Master LeetCode's Top K Frequent Elements problem with expert insights into optimal O(N) bucket sort, efficient O(N log K) min-heap, and advanced quickselect solutions for finding the most frequent items in an array.
LeetCode 347, “Top K Frequent Elements,” is one of those problems that looks deceptively simple at first glance. You’re given an array of integers and asked to return the k most frequent elements. Easy, right? Well, here’s the catch - the problem explicitly wants you to beat O(N log N) time complexity. That’s where things get interesting.
This constraint pushes you beyond basic sorting into some genuinely elegant algorithmic territory. We’ll explore multiple solutions, each with its own trade-offs and sweet spots.
Given an array nums and an integer k, find the k numbers that appear most often.
Let’s look at a couple examples:
nums = [1,1,1,2,2,3] and k = 2: The number 1 shows up 3 times, 2 appears twice, and 3 appears once. So we return [1,2].nums = [1] and k = 1: Just return [1].Pretty straightforward, but there’s more to unpack.
10^5 (that’s 100,000 elements)-10^4 to 10^4k is always valid (between 1 and the number of unique elements)That last point is the real kicker. It’s basically the problem saying “don’t just sort everything by frequency.”
Key Insight: Every solution boils down to two steps: count the frequencies, then pick the top k.
Before we jump into fancy algorithms, let’s talk about what every solution needs.
No matter which approach you pick, you’ll start by counting how many times each number appears. A hash map (dictionary, hash table - whatever you want to call it) is perfect for this:
Once you’ve got your frequencies, you need to efficiently select the k highest ones. This is the classic “top-k” problem, and it’s where different data structures really shine (or fall flat).
Real-World Analogy: Think about Amazon’s “Top Sellers” list. First, they count how many of each product sold (frequency counting). Then they identify the top-selling items (selecting top k). Same pattern.
Let’s walk through four different ways to solve this, from the most practical to the most theoretically optimal.
Here’s something that trips people up: we use a min-heap to find the max frequencies. Sounds backwards, right? But it’s actually brilliant.
Picture a VIP lounge that can only fit k people. Everyone has a popularity score (their frequency).
Here’s how it works:
k people inside), they get inBy the end, you’re guaranteed to have the k most popular people in the lounge.
The min-heap always keeps the least popular person at the top, making it super efficient to decide who to kick out.
k:k, remove the smallest frequencyWatch how the min-heap maintains the top k elements dynamically:
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// Step 1: Count frequencies
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
// Step 2: Build a min-heap of size k
// Store pairs as (frequency, number)
// The comparator ensures it's a min-heap based on frequency
PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
(a, b) -> a.getValue() - b.getValue()
);
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
minHeap.offer(entry);
if (minHeap.size() > k) {
minHeap.poll(); // Kick out the least frequent element
}
}
// Step 3: Extract results from the heap
int[] ans = new int[k];
for (int i = k - 1; i >= 0; --i) {
ans[i] = minHeap.poll().getKey();
}
return ans;
}
}Time Complexity: O(N log K)
Breaking it down:
Space Complexity: O(N)
The min-heap approach shines when k is much smaller than the total number of unique elements. It’s also a pattern that interviewers love because it shows you understand heap mechanics. If you can only remember one solution for an interview, make it this one.
Now we’re talking. Bucket sort gives us true linear time - O(N) - by exploiting a clever observation: frequencies are bounded by the array size.
Imagine you’ve got a set of shelves, each labeled with a number (0, 1, 2, … up to N).
k items, start from the highest shelf and grab items until you have k of themThe maximum possible frequency is N (if every element is the same), so you only need N+1 shelves total.
kSee how elements get sorted into frequency buckets:
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// Step 1: Count frequencies
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
// Step 2: Create buckets (array of lists)
// Index = frequency, max frequency = nums.length
List<Integer>[] buckets = new List[nums.length + 1];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
// Step 3: Distribute numbers into buckets
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
int num = entry.getKey();
int freq = entry.getValue();
buckets[freq].add(num);
}
// Step 4: Collect top K from highest frequency down
List<Integer> ans = new ArrayList<>();
for (int i = buckets.length - 1; i >= 0 && ans.size() < k; i--) {
for (int num : buckets[i]) {
ans.add(num);
if (ans.size() == k) {
return ans.stream().mapToInt(Integer::intValue).toArray();
}
}
}
return ans.stream().mapToInt(Integer::intValue).toArray();
}
}Time Complexity: O(N)
Here’s the breakdown:
Space Complexity: O(N)
This approach is theoretically optimal for this problem because:
Quickselect is the dark horse of this problem. It’s based on the same partitioning logic as Quicksort, but instead of sorting everything, it just finds the k-th element.
The beauty is that you don’t need to fully sort - you just keep partitioning until you’ve isolated the top k elements.
import random
from collections import Counter
class Solution:
def topKFrequent(self, nums: list[int], k: int) -> list[int]:
count = Counter(nums)
unique_elements = list(count.keys())
n_unique = len(unique_elements)
def quickselect(left, right, target_idx):
if left == right:
return
# Pick random pivot
pivot_idx = random.randint(left, right)
pivot_freq = count[unique_elements[pivot_idx]]
# Move pivot to end
unique_elements[pivot_idx], unique_elements[right] = unique_elements[right], unique_elements[pivot_idx]
# Partition: move smaller frequencies left
store_idx = left
for i in range(left, right):
if count[unique_elements[i]] < pivot_freq:
unique_elements[store_idx], unique_elements[i] = unique_elements[i], unique_elements[store_idx]
store_idx += 1
# Move pivot to final position
unique_elements[right], unique_elements[store_idx] = unique_elements[store_idx], unique_elements[right]
if target_idx == store_idx:
return
elif target_idx < store_idx:
quickselect(left, store_idx - 1, target_idx)
else:
quickselect(store_idx + 1, right, target_idx)
# Find the (n_unique - k)th element
# Everything from that position to the end will be our top k
quickselect(0, n_unique - 1, n_unique - k)
return unique_elements[n_unique - k:]
Time Complexity: O(N) average, O(N²) worst case
Space Complexity: O(N)
Quickselect is powerful, but its worst-case behavior and complexity make it less popular for this specific problem. It’s fantastic for finding medians or k-th values in general, though.
This is what you’d do if there were no time complexity constraints. It’s simple but usually too slow.
Here’s the frequency counting step that all approaches share:
This violates the problem’s requirement for better than O(N log N).
Space Complexity: O(N)
Don’t use this when the problem explicitly wants better than O(N log N), or when you’re dealing with massive datasets.
Here’s the quick reference guide:
| Approach | Time Complexity | Space Complexity | When to Use |
|---|---|---|---|
| Bucket Sort | O(N) | O(N) | Best overall - guaranteed linear time |
| Min-Heap | O(N log K) | O(N) | When k << N, great for interviews |
| Quickselect | O(N) avg, O(N²) worst | O(N) | Average O(N) but risky worst case |
| Sorting | O(N log N) | O(N) | Simple but too slow for this problem |
💡 My Take: For this problem specifically, Bucket Sort is the cleanest and most optimal. But if you’re in an interview and bucket sort feels tricky, the Min-Heap approach is totally solid and well-understood.
The problem guarantees a unique answer, so you won’t have ambiguous tie situations. If ties were possible and needed specific handling (like lexicographical order), you’d need to adjust your comparisons accordingly.
[1], k=1 → returns [1] ✓[5,5,5,5], k=1 → returns [5] ✓All approaches handle these naturally.
collections.Counter for frequency counting. The heapq module handles min-heaps nicely.HashMap + PriorityQueue with a custom Comparatorunordered_map + priority_queue (you’ll need a custom comparator struct)count, freq, bucket)Once you’ve got this down, try these:
Let me wrap this up with the key insights:
It’s always two steps: Count frequencies, then select top k. Every approach follows this pattern.
Bucket sort is king for this specific problem. When your “scores” (frequencies) are bounded by a known max (N), bucket sort gives you true O(N) time.
Min-heap is your interview friend. It’s O(N log K), well-understood, and works great when k is small.
Quickselect is powerful but risky. Average O(N) is great, but that O(N²) worst case can hurt.
Don’t just sort everything. The problem’s pushing you toward smarter selection algorithms for a reason.
Understanding these approaches doesn’t just help you solve this problem - it gives you a toolkit for tackling frequency analysis and top-k challenges across algorithms and system design. And trust me, you’ll see this pattern everywhere.