Top K Frequent Elements.md

Algorithm

1. Create HashMap of number frequencies. Frequency = # of times a number appears in array.
2. Create buckets, 1 for each possible frequency. Fill buckets with numbers from input, based on their frequency.
3. To get the most frequent elements, loop through the buckets in descending order.

Edge case: Two numbers can be tied for more frequent element. The problem doesn't say what to do in this case, so you should ask the interviewer about this.

Solution

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return Collections.<Integer>emptyList();
        }

        Map<Integer, Integer> map = new HashMap();
        for (int num : nums) {
            map.merge(num, 1, Integer::sum);
        }

        List<List<Integer>> buckets = new ArrayList(nums.length + 1); // wont use 0th bucket
        for (int i = 0; i < nums.length + 1; i++) {
            buckets.add(new ArrayList<Integer>());
        }

        for (Integer num : map.keySet()) {
            int frequency = map.get(num);
            List<Integer> bucket = buckets.get(frequency);
            bucket.add(num);
        }

        List<Integer> solution = new ArrayList();
        for (int i = buckets.size() - 1; i >= 0 && solution.size() < k; i--) {
            List<Integer> bucket = buckets.get(i);
            solution.addAll(bucket);
        }
        return solution.subList(0, k); // needed since above loop can add more than k elements into list
    }
}

Time/Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

Links

• github.com/RodneyShag