5. Top K Frequent Elements

Description

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]

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.

Approach 0

• So first create a frequency map with input integer as key and their frequency as value
• Now we will create an array whose elements are List<Integer> the purpose being frequency as key and the elements with that frequency stored as a List
• The size would be input array length as the most frequency someone can have is that
• So now we just iterate through this array in reverse and return k elements

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> freq = new HashMap<>();
        List<Integer>[] bucket = new ArrayList[nums.length + 1];
 
        for (int num: nums) {
            freq.put(num, freq.getOrDefault(num,0) + 1);
        }
 
        for (int key: freq.keySet()) {
            int count = freq.get(key);
            if(bucket[count] == null) {
                bucket[count] = new ArrayList<>();
            }
            bucket[count].add(key);
        }
 
        int index = 0;
        int[] res = new int[k];
        for(int i = nums.length; i >= 0; i--) {
            if(bucket[i] != null) {
                for(int val: bucket[i]) {
                    res[index++] = val;
                    if(index == k) {
                        return res;
                    }
                }
            }
        }
 
        return res;
    }
}

Approach 1: Max-Heap / Sorting

Intuition

Count the frequency of each element using a hash map. Push all unique numbers into a Max-Heap sorted by their frequency, then pop the top k elements.

import java.util.*;
 
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
 
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> countMap.get(b) - countMap.get(a));
        for (int num : countMap.keySet()) {
            maxHeap.add(num);
        }
 
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll();
        }
        return result;
    }
}
 

Complexity

• Time Complexity: $O(U\log U)$ — Where $U$ is the number of unique elements in nums. In the worst case $U=N$.
• Space Complexity: $O(U)$ — Map and heap store up to $U$ unique elements.

---

Approach 2: Min-Heap of Size $k$

Intuition

Build a frequency map. Instead of storing all unique elements in a Max-Heap, maintain a Min-Heap of size at most k. If the heap grows past size k, pop the least frequent element. When done, the heap holds the top k most frequent elements.

import java.util.*;
 
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
 
        // Min-Heap ordered by frequency
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> countMap.get(a) - countMap.get(b));
 
        for (int num : countMap.keySet()) {
            minHeap.add(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // Evict the element with the lowest frequency
            }
        }
 
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = minHeap.poll();
        }
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N+U\log k)$ — $O(N)$ to build frequency map, $O(U\log k)$ to maintain Min-Heap of size $k$.
• Space Complexity: $O(U+k)$ — Map stores $U$ elements and heap stores up to $k$ elements.

---

Most Optimized Solution: Bucket Sort ($O(N)$ Time)

Intuition

Since an element can appear at most $N$ times, create an array of lists bucket of size $N+1$, where index i holds elements that appear exactly i times. Iterate backwards from frequency $N$ down to $1$ to collect the top k frequent numbers.

import java.util.*;
 
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
 
        // Index = frequency, Value = list of numbers with that frequency
        List<Integer>[] bucket = new List[nums.length + 1];
 
        for (int key : countMap.keySet()) {
            int freq = countMap.get(key);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(key);
        }
 
        int[] result = new int[k];
        int index = 0;
 
        // Traverse backwards from highest possible frequency
        for (int i = bucket.length - 1; i >= 0 && index < k; i--) {
            if (bucket[i] != null) {
                for (int num : bucket[i]) {
                    result[index++] = num;
                    if (index == k) {
                        return result;
                    }
                }
            }
        }
 
        return result;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Linear scan to count frequencies and populate buckets.
• Space Complexity: $O(N)$ — Buckets and frequency map store at most $N$ elements.

---

Easy Memory Rule

“Frequency map $\to$ Array of Buckets where index = frequency $\to$ Traverse from back to front until $k$ items collected.”