Top K Frequent Elements (LeetCode 347) – Complete Interview Guide

This is a classic and highly frequent interview question at FAANG companies. It tests your ability to optimize time and space complexity using foundational data structures. Let's break it down step-by-step so you can master not just the solution, but the reasoning behind it.

1. 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.

Definitions & Constraints

• Input: An array of integers (nums) and an integer (k).
• Output: An array of k integers representing the most frequent elements.
• Frequency: The number of times a specific integer appears in the array.
• Duplicates Allowed: Yes, the array will contain duplicates.
• Negative Numbers: Yes, they are allowed and valid.
• Is K always valid? Yes. 1≤k≤ number of unique elements.
• Output Order: Does not matter.

Example

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

Why? * 1 appears 3 times.

• 2 appears 2 times.
• 3 appears 1 time.
• The top 2 most frequent numbers are 1 and 2.

2. Brute Force Solution

Intuition

The simplest approach is to count how many times each number appears, sort the numbers based on their counts from highest to lowest, and pick the first k numbers.

Algorithm

1. Count: Iterate through the array and store the frequency of each element in a Hash Map.
2. Store: Transfer the map's contents (element-frequency pairs) into an array/list.
3. Sort: Sort this list in descending order based on the frequencies.
4. Extract: Pick the first k elements from the sorted list.

Complete Dry Run

• Original array: [1,1,1,2,2,3]
• Frequency Map: {1: 3, 2: 2, 3: 1}
• Frequency List: [(1,3), (2,2), (3,1)] (format: value, frequency)
• Sorting (by freq descending): [(1,3), (2,2), (3,1)]
• First K (k=2) Elements:[1, 2]

C++ Implementation

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Step 1: Count frequencies of each number
        unordered_map<int, int> freqMap;
        for (int num : nums) {
            freqMap[num]++;  // increment frequency count for each number
        }
        
        // Step 2: Store (number, frequency) pairs in a vector
        vector<pair<int, int>> freqList;
        for (auto const& [num, freq] : freqMap) {
            freqList.push_back({num, freq});  // push pair into vector
        }
        
        // Step 3: Sort the vector by frequency in descending order
        sort(freqList.begin(), freqList.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.second > b.second;  // compare based on frequency
        });
        
        // Step 4: Extract the top K frequent numbers
        vector<int> result;
        for (int i = 0; i < k; ++i) {
            result.push_back(freqList[i].first);  // take the number part of the pair
        }
        
        return result;  // return the list of top K frequent numbers
    }
};

Complexity Analysis

• Time Complexity: $O(N \log N)$ where $N$ is the number of elements. Building the map takes $O(N)$, but sorting the unique elements takes up to $O(N \log N)$ in the worst case where all elements are unique.
• Space Complexity: $O(N)$ to store the map and the array.

Advantages & Disadvantages

• Advantages: Very easy to understand, implement, and explain.
• Disadvantages: Unnecessary work. Sorting the entire array of frequencies is overkill when we only care about the top k.

Why We Need a Better Solution

If you have 1 million unique numbers and only need the top 3, sorting all 1 million is a massive waste of processing power. We need a way to filter for the top k without a full sort.

3. Better Solution (Partial Sorting)

Intuition

Instead of fully sorting the array, C++ has a built-in function called nth_element. It rearranges the array so that the element at the k-th position is the one that would be there if the array was fully sorted. It also guarantees that all elements before it are strictly greater (if sorting descending).

Algorithm

1. Build the frequency map.
2. Transfer pairs to a vector.
3. Use std::nth_element to partially sort the array up to the k-th index.
4. Extract the first k elements.

Complete Dry Run

• Original: [1,1,1,2,2,3] -> Map: {1:3, 2:2, 3:1}
• List: [(3,1), (2,2), (1,3)] (unordered map output might vary)
• nth_element for k=2: Rearranges list so the top 2 frequencies are at the front.
• List becomes: [(1,3), (2,2), (3,1)]

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Step 1: Count frequencies of each number
        unordered_map<int, int> freqMap;
        for (int num : nums) {
            freqMap[num]++;  // increment frequency count for each number
        }
        
        // Step 2: Store (number, frequency) pairs in a vector
        vector<pair<int, int>> freqList;
        for (auto const& [num, freq] : freqMap) {
            freqList.push_back({num, freq});  // push pair into vector
        }
        
        // Step 3: Use nth_element for partial sorting
        // nth_element rearranges the vector so that the element at position k-1
        // is the one that would be there if the vector were fully sorted.
        // All elements before it are greater (in this case, higher frequency),
        // and all elements after it are smaller.
        nth_element(freqList.begin(), freqList.begin() + k - 1, freqList.end(), 
            [](const pair<int, int>& a, const pair<int, int>& b) {
                return a.second > b.second; // compare by frequency descending
            });
            
        // Step 4: Extract the top K frequent numbers
        vector<int> result;
        for (int i = 0; i < k; ++i) {
            result.push_back(freqList[i].first);  // take the number part of the pair
        }
        
        return result;  // return the list of top K frequent numbers
    }
};

Complexity Analysis

• Time Complexity: Average $O(N)$, Worst-case $O(N^2)$. nth_element uses Introselect.
• Space Complexity: $O(N)$.

Advantages & Disadvantages

• Advantages: Average case is linear time! Extremely fast in practice.
• Disadvantages: In an interview, relying on a language-specific black-box function like nth_element often misses the point of the question. The worst-case time complexity is also $O(N^2)$.

Why We Still Need Something Better

Interviewers want to see you manipulate data structures to solve the problem predictably. We need an approach that guarantees better worst-case time than partial sorting and doesn't rely on language internals.

4. Optimal Solution (Min Heap)

Intuition

Suppose there are $M$ unique numbers. We only need the $K$ most frequent ones.

Instead of sorting everything, imagine keeping a "Top K" leaderboard. As you evaluate each candidate, if they have a higher score than the lowest person on the leaderboard, the lowest person gets kicked off, and the new candidate joins.

A Min Heap perfectly models this leaderboard.

Key Observations

• We only care about the $K$ highest frequencies.
• If we keep a Min Heap of size $K$, the element at the top is the smallest of the top K.
• When a new element arrives, we push it into the heap. If the heap size exceeds $K$, we pop the top element (the smallest frequency).
• By the end, the elements that survived in the heap are the $K$ largest.

Why Min Heap?

• Why not Max Heap? A Max Heap would require pushing all elements in to find the max, which takes $O(N \log N)$ space and time.
• Why Min Heap of size K? We only process operations on a heap of size $K$. This drops the insertion cost from $O(\log N)$ to $O(\log K)$.

ASCII Diagram

Assume K = 3. The heap maintains the top 3 frequencies we've seen so far.

Current Heap (Size = 3)
      (3)   <-- Smallest of the top K is at the top
     /   \
   (5)   (8)

Next element has frequency 6.
Insert 6:
       (3)
      /   \
    (5)   (8)
   /
 (6)

Heap size is now 4 (which is > 3). Remove the top (3).
Heap adjusts:
       (5)
      /   \
    (6)   (8)

Algorithm

1. Build Map: Traverse array, count frequencies.
2. Maintain Min Heap: Traverse the map. Insert (frequency, value) into a Min Heap.
3. Trim: Whenever the heap size exceeds k, pop the top element.
4. Extract: Pop the remaining k elements into the result array.

C++ implementation

#include <vector>
#include <unordered_map>
#include <queue>

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Step 1: Build the frequency map
        unordered_map<int, int> freqMap;
        for (int num : nums) {
            freqMap[num]++;  // count how many times each number appears
        }
        
        // Step 2: Use a Min Heap to keep track of the top k elements
        // priority_queue in C++ is a Max Heap by default.
        // We use greater<> to make it a Min Heap.
        // Store pairs as {frequency, number}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
        
        for (auto const& [num, freq] : freqMap) {
            minHeap.push({freq, num});  // push {frequency, number} into heap
            
            // Step 3: If heap size exceeds k, remove the smallest frequency
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        
        // Step 4: Extract the top k frequent numbers from the heap
        vector<int> result;
        while (!minHeap.empty()) {
            result.push_back(minHeap.top().second);  // take the number part
            minHeap.pop();
        }
        
        return result;  // return the list of top k frequent numbers
    }
};

5. Complete Dry Run

Input: nums = [1,1,1,2,2,3,4,4,4,4], k = 2 Frequency Map: {1: 3, 2: 2, 3: 1, 4: 4}

K = 2

------------------------------------------------------------
Insert (freq = 3, value = 1)

Heap after insertion:
[(3,1)]

Heap Size : 1
Trigger Pop? : No

Final Heap:
[(3,1)]
------------------------------------------------------------

Insert (freq = 2, value = 2)

Heap after insertion:
[(2,2), (3,1)]

Heap Size : 2
Trigger Pop? : No

Final Heap:
[(2,2), (3,1)]
------------------------------------------------------------

Insert (freq = 1, value = 3)

Heap after insertion:
[(1,3), (2,2), (3,1)]

Heap Size : 3
Trigger Pop? : Yes
Pop -> (1,3)

Final Heap:
[(2,2), (3,1)]
------------------------------------------------------------

Insert (freq = 4, value = 4)

Heap after insertion:
[(2,2), (4,4), (3,1)]

Heap Size : 3
Trigger Pop? : Yes
Pop -> (2,2)

Final Heap:
[(3,1), (4,4)]
------------------------------------------------------------

Final Top K Frequent Elements:
[(3,1), (4,4)]

Values = [1, 4]

Remaining elements in heap: 1 (freq 3) and 4 (freq 4).

Output: [1, 4]

6. Correctness Proof

• Invariant: At any point, the Min Heap holds the $K$ highest frequencies seen so far.
• Step Proof: 1. We add a new element to the heap. The heap now contains $K+1$ elements.2. Because it is a Min Heap, the smallest element of these $K+1$ items sits at the top.3. We pop the top. The element removed is mathematically guaranteed to NOT be in the top $K$ of this subset.4. Therefore, the remaining $K$ elements are strictly the largest $K$ elements seen so far.
• Conclusion: Once all elements are processed, the surviving $K$ elements must be the global top $K$.

7. Complexity Analysis

• Building frequency map: $O(N)$ time.
• Heap operations: In the worst case, there are $U$ unique elements. We push all $U$ elements into the heap. Pushing into a heap of size $K$ takes $O(\log K)$ time. Total heap time: $O(U \log K)$.
• Overall Time Complexity: $O(N + U \log K)$. Because $U \le N$, this is strictly better than $O(N \log N)$.
• Overall Space Complexity: $O(U + K)$ for the map and the heap.

8. Edge Cases

• Empty array / invalid K: Constraints usually guarantee valid inputs, but checking if (nums.empty()) return {}; is safe.
• K = Number of unique elements: The heap will grow to size $N$ and no elements will be popped. The algorithm behaves perfectly.
• Negative numbers: Keys in our hash map seamlessly handle negative numbers.
• Large data streams: If data cannot fit into memory, Min Heap is perfect because we process it element by element, only maintaining a heap of size $K$ in RAM.

9. Common Interview Mistakes

• Using a Max Heap: Candidates naturally hear "Top K" and think "Max". Putting all elements into a Max Heap and popping $K$ times takes $O(N \log N)$ space/time. Min Heap is an optimization pattern.
• Storing just the frequency: You must store (frequency, value) pairs in the heap. If you only store frequency, you won't know which original number it belonged to.
• Wrong map traversal: Iterating over nums to insert into the heap instead of iterating over the freqMap. You must consolidate the counts first!
• Pair Ordering: In C++, std::pair sorts by the first element, then the second. You must format your pair as (frequency, value), not (value, frequency).

11. Alternative Optimal Solution (Bucket Sort)

Intuition

Is there a way to solve this in $O(N)$ time without sorting? Yes.

The maximum possible frequency of any element is $N$ (the length of the array). We can create an array of "buckets" where the index of the bucket represents the frequency, and the contents of the bucket are the numbers that appear that many times.

Algorithm

1. Build the frequency map.
2. Create an array of lists (buckets) of size $N+1$.
3. For every (num, freq) in the map, place num into buckets[freq].
4. Iterate through the buckets backwards (from highest frequency $N$ down to 0).
5. Collect numbers until you have k elements.

C++ Code

#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Step 1: Build the frequency map
        unordered_map<int, int> freqMap;
        for (int num : nums) {
            freqMap[num]++;  // count occurrences of each number
        }
        
        int n = nums.size();
        // Step 2: Create buckets where index = frequency
        // Each bucket stores numbers that appear 'index' times
        vector<vector<int>> buckets(n + 1); 
        
        for (auto const& [num, freq] : freqMap) {
            buckets[freq].push_back(num);  // place number in its frequency bucket
        }
        
        // Step 3: Traverse buckets backwards (from highest frequency to lowest)
        vector<int> result;
        for (int i = n; i >= 0 && result.size() < k; --i) {
            for (int num : buckets[i]) {
                result.push_back(num);  // collect numbers with high frequency
                if (result.size() == k) return result;  // stop once we have k elements
            }
        }
        
        return result;  // return the list of top k frequent numbers
    }
};

Complexity Analysis

• Time Complexity: $O(N)$. Map building is $O(N)$. Placing into buckets is $O(U)$. Traversing buckets is $O(N)$.
• Space Complexity: $O(N)$. The map takes $O(U)$ and the buckets take $O(N)$.

Advantages & Disadvantages

• Advantages: Strictly $O(N)$ time, beating the heap's $O(N \log K)$.
• Disadvantages: High memory overhead. If you have an array of 1 million elements and all are unique, you create 1 million buckets, but 999,999 of them are empty.

Why Min Heap is preferred: While Bucket Sort is technically $O(N)$, the Min Heap solution extends beautifully to real-world system design questions (like finding the Top K trending tweets in a massive stream of data where you can't hold everything in memory). Interviewers love the Min Heap approach.

13. Interview Tips

• The "Top K" Trigger: Whenever an interviewer says "Find the Top K", "Largest K", or "Most frequent K", immediately say: "This sounds like a problem we can optimize using a Heap."
• Top K Largest vs Smallest:
  • To find Top K Largest/Most Frequent, use a Min Heap. (Eject the small ones).
  • To find Top K Smallest, use a Max Heap. (Eject the large ones).
• Explaining Intuition: Don't just start writing code. Draw the ASCII leaderboard diagram. Explain the flaw of the Brute Force method ("sorting things we don't care about") to motivate your optimal solution.
• Common Follow-Up: "What if the data is so large it doesn't fit in memory?" -> Explain that you can compute frequencies in chunks using MapReduce, and then pipe the results into a single Min Heap of size K, which takes virtually zero memory.

Video reference:

problem link:

https://leetcode.com/problems/top-k-frequent-elements/