Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Example 3:

Input: nums = [1,2,1,2,1,2,3,1,3,2], k = 2

Output: [1,2]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Follow up: Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

Approach: HashMap + Min-Heap

Algorithm

1. Count the frequency of each number with a hash map
2. Keep a min-heap of size k; for each (number, frequency) pair, insert it and evict the smallest when the heap exceeds k
3. The heap at the end contains the k most frequent elements

Time & Space Complexity

• Time Complexity: O(n log k) - counting takes O(n), each heap operation costs O(log k)
• Space Complexity: O(n) - the frequency map (plus O(k) for the heap)

Java Implementation

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class TopKFrequentElements {

    /**
     * Return the k most frequent elements.
     * @param nums Input array
     * @param k Number of top elements
     * @return List of the k most frequent elements
     */
    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);
        }

        PriorityQueue<Integer> heap = new PriorityQueue<>(
                (a, b) -> count.get(a) - count.get(b));

        for (int num : count.keySet()) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = heap.poll();
        }
        return result;
    }

    // Test method
    public static void main(String[] args) {
        TopKFrequentElements t = new TopKFrequentElements();
        System.out.println("Input: nums = [1,1,1,2,2,3], k = 2");
        System.out.println("Output: " + java.util.Arrays.toString(t.topKFrequent(new int[]{1, 1, 1, 2, 2, 3}, 2)));
        // Expected: [1,2]

        System.out.println("Input: nums = [1], k = 1");
        System.out.println("Output: " + java.util.Arrays.toString(t.topKFrequent(new int[]{1}, 1)));
        // Expected: [1]
    }
}

Alternative Approach: Bucket Sort by Frequency

public int[] topKFrequentBucket(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 (Map.Entry<Integer, Integer> entry : count.entrySet()) {
        int freq = entry.getValue();
        if (buckets[freq] == null) {
            buckets[freq] = new ArrayList<>();
        }
        buckets[freq].add(entry.getKey());
    }

    List<Integer> result = new ArrayList<>();
    for (int freq = buckets.length - 1; freq > 0 && result.size() < k; freq--) {
        if (buckets[freq] != null) {
            result.addAll(buckets[freq]);
        }
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

Example Walkthrough

For nums = [1,1,1,2,2,3], k = 2:

1. Frequencies: 1->3, 2->2, 3->1
2. Heap of size 2: insert 1 (freq 3), 2 (freq 2), then 3 (freq 1) evicts the smallest -> heap holds {1, 2}
3. Result: [1, 2]

Key Points

1. Frequency First: A hash map converts the problem to top-k by frequency
2. Min-Heap of Size k: Evicting the minimum keeps only the k largest at O(n log k)
3. Better than O(n log n): The heap approach and the bucket approach both satisfy the follow-up
4. Bucket Sort: Frequency is bounded by n, so buckets indexed by frequency run in O(n)
5. Unique Answer: The problem guarantees a unique set, so any order is accepted