Log inSign up
mediumLeetCodeNot Started

Top K Frequent Elements

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Heap
Solve on LeetCode
Lesson

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.

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

Example 1 · Example 1: Top 2 Elements:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1, 2]
Explanation: Frequencies: 1 appears 3 times, 2 appears 2 times, 3 appears 1 time. The 2 most frequent elements are 1 and 2. Bucket Array: Index 1: [3] Index 2: [2] Index 3: [1] Traversing from top: [1, 2].

Example 2 · Example 2: Single Element:

Input: nums = [1], k = 1
Output: [1]
Explanation: Only 1 element exists; returns [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.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand why Bucket Sort can replace priority queues when keys are bounded.
  • Implement the Min-Heap size-K pattern for top-K problems.
  • Construct reverse bucket traversals in all 4 languages.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Find Top K most frequent elements.
  • Time complexity must be strictly better than O(N log N).
  • Unique answer guaranteed.

Algorithmic Decision Tree:

  • Min-Heap of size K provides O(N log K) time.
  • Bucket Sort provides O(N) linear time and is the gold-standard optimal choice.

Connected Patterns:

Top K Frequent WordsFrequency SortKth Largest Element in an Array

1. Brute Force — Frequency Map & Sort

Intuition

Build frequency map. Extract unique keys into a list and sort by their frequency descending. Return the first k elements.

When to apply: When simplicity is desired and N is small.

Algorithm

  1. Step 1: Count frequency of each number in nums.
  2. Step 2: Extract unique elements into a list.
  3. Step 3: Sort list by freq[b] - freq[a].
  4. Step 4: Return first k elements.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> topKFrequent(vector<int>& nums, int k) {
10 unordered_map<int, int> freq;
11 for (int x : nums) freq[x]++;
12
13 vector<pair<int, int>> pairs;
14 for (auto& [val, count] : freq) {
15 pairs.push_back({count, val});
16 }
17 sort(pairs.rbegin(), pairs.rend());
18
19 vector<int> result;
20 for (int i = 0; i < k; i++) {
21 result.push_back(pairs[i].second);
22 }
23 return result;
24 }
25};
26
27int main() {
28 Solution sol;
29 vector<int> nums = {1, 1, 1, 2, 2, 3};
30 auto res = sol.topKFrequent(nums, 2);
31 cout << "Top K Frequent (Brute Force): ";
32 for (int x : res) cout << x << " ";
33 cout << endl;
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(N + U log U) — O(N + U log U) sorting unique keys.
  • Space complexity: O(U) — O(U) hash map storage.

Why Brute Force Doesn't Scale:

With N = 105, sorting takes ~1.7 * 106 comparisons. Bucket Sort takes exactly 105 operations.

Bucket Sort runs in ~8ms for 100,000 integers.

2. Better — Min-Heap of Size K

Intuition

Count frequencies using hash map. Push pairs of (freq, val) into a Min-Heap. If heap size exceeds K, pop the root. The remaining K elements are the most frequent.

When to apply: When memory is bounded by K or stream of unique elements is processed.

Algorithm

  1. Step 1: Compute frequencies using hash map.
  2. Step 2: Maintain Min-Heap of capacity K comparing frequencies.
  3. Step 3: For each (val, count) in map: push (count, val) to heap.
  4. Step 4: If heap size > k: pop root.
  5. Step 5: Collect all values from heap and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <queue>
5using namespace std;
6
7class Solution {
8public:
9 vector<int> topKFrequent(vector<int>& nums, int k) {
10 unordered_map<int, int> freq;
11 for (int x : nums) freq[x]++;
12
13 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
14 for (auto& [val, count] : freq) {
15 minHeap.push({count, val});
16 if ((int)minHeap.size() > k) {
17 minHeap.pop();
18 }
19 }
20
21 vector<int> result;
22 while (!minHeap.empty()) {
23 result.push_back(minHeap.top().second);
24 minHeap.pop();
25 }
26 return result;
27 }
28};
29
30int main() {
31 Solution sol;
32 vector<int> nums = {1, 1, 1, 2, 2, 3};
33 auto res = sol.topKFrequent(nums, 2);
34 cout << "Top K Frequent (Min-Heap): ";
35 for (int x : res) cout << x << " ";
36 cout << endl;
37 return 0;
38}

Time & Space Complexity

  • Time complexity: O(N + U log K) — O(N log K) bounded by heap size K.
  • Space complexity: O(U) — O(U) hash map and heap space.

3. Optimal — Bucket Sort (Linear O(N) Time)

Intuition

Since no element can appear more than N times, allocate an array of buckets of size N + 1. Store each unique element in bucket[freq]. Iterate from bucket N down to 1, collecting elements until k elements are found.

When to apply: Standard optimal solution achieving linear time.

Algorithm

  1. Step 1: Count frequency of each number in hash map.
  2. Step 2: Initialize bucket array of size nums.length + 1.
  3. Step 3: For each (num, count) in map: add num to bucket[count].
  4. Step 4: Traverse bucket from N down to 1; append numbers to result until result.length == k.
  5. Step 5: Return result.

Interactive Trace for Top K Frequent Elements

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Count map: {1: 3, 2: 2, 3: 1}
Visual state
Values and pointers at this exact step
tree
Root: (f:2, v:2)
2
Child: (f:3, v:1)
1

Node order shown; add connections to display explicit tree edges.

root: h1
Check / comparison
Heap size = 2. Root is (freq 2, val 2).
Decision / next transition
Next element will be compared with frequency 2.
Why this step matters

Step 1: Count map: {1: 3, 2: 2, 3: 1}. Push (3, 1) and (2, 2) into Min-Heap of size k=2.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
6class Solution {
7public:
8 vector<int> topKFrequent(vector<int>& nums, int k) {
9 unordered_map<int, int> freq;
10 for (int x : nums) freq[x]++;
11
12 int n = nums.size();
13 vector<vector<int>> buckets(n + 1);
14 for (auto& [val, count] : freq) {
15 buckets[count].push_back(val);
16 }
17
18 vector<int> result;
19 for (int i = n; i >= 1 && (int)result.size() < k; i--) {
20 for (int val : buckets[i]) {
21 result.push_back(val);
22 if ((int)result.size() == k) break;
23 }
24 }
25 return result;
26 }
27};
28
29int main() {
30 Solution sol;
31 vector<int> nums = {1, 1, 1, 2, 2, 3};
32 auto res = sol.topKFrequent(nums, 2);
33 cout << "Top K Frequent (Bucket Sort): ";
34 for (int x : res) cout << x << " ";
35 cout << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N) — O(N) linear time with zero comparison sorting.
  • Space complexity: O(N) — O(N) memory for buckets and frequency map.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Frequency Map & Full SortO(N log N)O(N)Count frequencies with hash map. Sort unique elements descending by frequency, take first k.Full sorting.
2.Better — Min-Heap of Size KO(N log K)O(N)Count frequencies. Push (freq, num) into a Min-Heap of size K. Root holds minimum among top K.Heap operations.
3.Optimal — Bucket Sort (Frequency Buckets)OptimalO(N)O(N)Count frequencies. Place elements in bucket[freq]. Traverse buckets from N down to 1.None. Perfectly optimal.

Common Pitfalls & Crucial Edge Cases

Using Max-Heap of size N

Takes O(N + K log N) time and O(N) space; Min-Heap of size K is preferred.

Buckets index out of bounds

Bucket size must be N + 1 because frequency can be equal to N.

Overwriting buckets with a single element

Multiple numbers can share identical frequencies; each bucket must be a list.

Crucial Edge Cases to Validate:

  • k == unique elements — Returns all unique elements.
  • All elements have identical frequency — Any k elements are valid.
  • Single element array (N = 1) — Returns [nums[0]].
  • Negative numbers — Handled properly by hash map keys.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention Min-Heap (O(N log K)) first, then demonstrate mastery with Bucket Sort (O(N)).
  2. Emphasize that the answer requires 'better than O(N log N)', which both approaches satisfy.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Bucket Sort achieve O(N) time for Top K Frequent Elements?

Back to DSA Sheet