225. Top K Frequent Elements

Count frequencies with a hash map, then use bucket sort where index = frequency. Walk buckets from high to low to collect top k.

Approach

1. Count frequency of each element.
2. Create buckets where bucket[i] = elements with frequency i.
3. Walk from highest bucket downward, collecting elements until we have k.

Complexity

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

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        List<Integer>[] buckets = new List[nums.length + 1];
        for (int i = 0; i < buckets.length; i++) {
            buckets[i] = new ArrayList<>();
        }
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            buckets[entry.getValue()].add(entry.getKey());
        }

        int[] result = new int[k];
        int idx = 0;
        for (int i = buckets.length - 1; i > 0 && idx < k; i--) {
            for (int num : buckets[i]) {
                result[idx++] = num;
                if (idx == k) return result;
            }
        }
        return result;
    }
}