Approach

Top K Frequent Elements

Problem Statement

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

Approach 1: Heap (Priority Queue)

Use a hash map to count frequencies, then use a min-heap to track top k elements.

Algorithm

Count frequencies: Build hash map of element → frequency
Use min-heap of size k:
- Add elements to heap
- If heap size exceeds k, remove minimum
Return heap contents: These are the k most frequent

Time Complexity

Time: O(n log k) where n is array length
- O(n) to count frequencies
- O(n log k) to maintain heap of size k
Space: O(n) for hash map

Approach 2: Bucket Sort

More efficient approach using bucket sort concept.

Algorithm

Count frequencies: Build hash map
Create buckets: Array where index = frequency
Populate buckets: bucket[freq] = list of elements with that frequency
Collect from end: Iterate from highest frequency, collect k elements

Time Complexity

Time: O(n) - linear time!
Space: O(n) for buckets

Example

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

Frequency map:
1: 3, 2: 2, 3: 1

Buckets (index = frequency):
[0]: []
[1]: [3]
[2]: [2]
[3]: [1]

Collect from end: [1, 2] (top 2 most frequent)

Key Insights

Bucket sort is optimal: O(n) time
Heap approach is more intuitive but slower
Frequency must be ≤ n, so bucket array size is bounded
Order doesn't matter in result
Can use Counter in Python for cleaner code

Solution

java

1/**
2 * Top K Frequent Elements
3 * Time: O(n) with bucket sort, O(n log k) with heap
4 * Space: O(n)
5 */
6
7import java.util.*;
8
9// Approach 1: Bucket Sort (Optimal)
10class Solution {
11    public int[] topKFrequent(int[] nums, int k) {
12        // Count frequencies
13        Map<Integer, Integer> count = new HashMap<>();
14        for (int num : nums) {
15            count.put(num, count.getOrDefault(num, 0) + 1);
16        }
17        
18        // Create buckets
19        List<Integer>[] buckets = new List[nums.length + 1];
20        for (int i = 0; i < buckets.length; i++) {
21            buckets[i] = new ArrayList<>();
22        }
23        
24        for (int num : count.keySet()) {
25            int freq = count.get(num);
26            buckets[freq].add(num);
27        }
28        
29        // Collect k most frequent
30        int[] result = new int[k];
31        int idx = 0;
32        for (int i = buckets.length - 1; i >= 0 && idx < k; i--) {
33            for (int num : buckets[i]) {
34                result[idx++] = num;
35                if (idx == k) return result;
36            }
37        }
38        
39        return result;
40    }
41}
42
43// Approach 2: Heap
44class Solution2 {
45    public int[] topKFrequent(int[] nums, int k) {
46        Map<Integer, Integer> count = new HashMap<>();
47        for (int num : nums) {
48            count.put(num, count.getOrDefault(num, 0) + 1);
49        }
50        
51        PriorityQueue<Integer> heap = new PriorityQueue<>(
52            (a, b) -> count.get(a) - count.get(b)
53        );
54        
55        for (int num : count.keySet()) {
56            heap.offer(num);
57            if (heap.size() > k) {
58                heap.poll();
59            }
60        }
61        
62        int[] result = new int[k];
63        for (int i = 0; i < k; i++) {
64            result[i] = heap.poll();
65        }
66        
67        return result;
68    }
69}
70