Top K Frequent Elements

Problem

Given a non-empty array of integers, return the k most frequent elements.

For example, Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: You may assume k is always valid, 1 ≤ k ≤ number of unique elements. Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Solution

public class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) { 
        List<Integer> res = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) map.put(num, map.getOrDefault(num, 0) + 1);
        map.entrySet()
            .stream()
            .sorted(Map.Entry.comparingByValue(Collections.reverseOrder()))
            .forEach(entry -> res.add(entry.getKey()));
        return res.subList(0, k);
    }
}

Analysis

A typical sorting HashMap by Value solution
We use map.entrySet().stream() to get the stream of Map.Entry
Then we call sorted(Map.Entry.comparingByValue()) on the stream
Because we need reverse order, we pass Collections.reverseOrder() as a parameter
Then we call forEach() to get each entry and add it to our res
At the end, we use subList(start, end) to get required result