278. Top K Frequent Elements
🔗 LeetCode Problem: 347. Top K Frequent Elements
📊 Difficulty: Medium
🏷️ Topics: Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect
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.
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 <= 10^5
- -10^4 <= nums[i] <= 10^4
- k is in the range [1, the number of unique elements in the array]
- It is guaranteed that the answer is unique
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
🌟 Understanding the Problem
What are we finding?
Input: [1,1,1,2,2,3]
Frequencies:
1 appears 3 times
2 appears 2 times
3 appears 1 time
k = 2 (want 2 most frequent)
Sorted by frequency (descending):
1 (freq=3) ← most frequent
2 (freq=2) ← 2nd most frequent
3 (freq=1)
Answer: [1, 2]
Key Observations:
1. Need to COUNT frequencies
→ Use HashMap: number → frequency
2. Need TOP K by frequency
→ Sort? Heap? Bucket sort?
3. Order doesn't matter in result
→ [1,2] and [2,1] both correct
→ This gives us flexibility!
4. Follow-up wants better than O(n log n)
→ Sorting is O(n log n)
→ Can we do O(n)?
🌟 The Natural Thinking Process
When you first see this problem:
Question: Find k most frequent elements
First Thought: "Count frequencies, then sort by frequency"
Step 1: Count with HashMap
Step 2: Sort by frequency
Step 3: Take top k
Is this optimal? NO (O(n log n)), but it WORKS!
Let's try it first.
The Evolution:
BRUTE FORCE THINKING:
"Count frequencies → Sort by count → Take k"
Time: O(n log n) for sorting
Problem: Follow-up wants better!
⬇
REALIZATION 1:
"I don't need FULL sort, just TOP K!"
"Similar to Kth Largest Element problem!"
"Use MIN-HEAP of size k!"
⬇
OPTIMIZATION 1: Min-Heap
"Keep heap of size k with k most frequent"
"Min-heap evicts least frequent easily"
Time: O(n log k) - better when k << n!
But follow-up wants O(n)...
⬇
REALIZATION 2:
"Frequency is bounded! Max freq = n"
"What if I create buckets by frequency?"
"Bucket i contains elements with frequency i"
⬇
OPTIMIZATION 2: Bucket Sort
"Create n+1 buckets (freq 0 to n)"
"Put each element in its frequency bucket"
"Collect from high frequency to low"
Time: O(n) - OPTIMAL! ✨
🎯 Approach 1: Brute Force - Sort by Frequency ⭐
The First Natural Solution
The Thought Process:
Step 1: Read problem
"Find k most frequent elements"
Step 2: How to find frequency?
"Count with HashMap"
Key: number, Value: frequency
Step 3: How to find most frequent?
"Sort by frequency (descending)"
"Take first k elements"
This is O(n log n), but let's code it first!
Visual Tracking - Complete Example
Input: nums = [1,1,1,2,2,3], k = 2
═══════════════════════════════════════════════════════════════
STEP 1: Count Frequencies
═══════════════════════════════════════════════════════════════
Process array element by element:
nums[0] = 1: map = {1: 1}
nums[1] = 1: map = {1: 2}
nums[2] = 1: map = {1: 3}
nums[3] = 2: map = {1: 3, 2: 1}
nums[4] = 2: map = {1: 3, 2: 2}
nums[5] = 3: map = {1: 3, 2: 2, 3: 1}
Final frequency map:
1 → 3
2 → 2
3 → 1
═══════════════════════════════════════════════════════════════
STEP 2: Create List of (number, frequency) Pairs
═══════════════════════════════════════════════════════════════
From map, create list:
[(1, 3), (2, 2), (3, 1)]
═══════════════════════════════════════════════════════════════
STEP 3: Sort by Frequency (Descending)
═══════════════════════════════════════════════════════════════
Sort by frequency (second element of pair):
Before sort: [(1, 3), (2, 2), (3, 1)]
After sort: [(1, 3), (2, 2), (3, 1)]
↑ freq=3 ↑ freq=2 ↑ freq=1
highest lowest
═══════════════════════════════════════════════════════════════
STEP 4: Take Top K Elements
═══════════════════════════════════════════════════════════════
k = 2
Take first 2 elements:
(1, 3) → number is 1
(2, 2) → number is 2
Result: [1, 2] ✓
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
Top 2 frequent elements: [1, 2]
Verification:
1 appears 3 times ← most frequent ✓
2 appears 2 times ← 2nd most frequent ✓
3 appears 1 time ← not in top 2
Implementation
import java.util.*;
/**
* Brute Force: Sort by frequency
* Time: O(n log n)
* Space: O(n)
*/
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// Step 1: Count frequencies
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// Step 2: Create list of (number, frequency) pairs
List<int[]> pairs = new ArrayList<>();
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
pairs.add(new int[]{entry.getKey(), entry.getValue()});
}
// Step 3: Sort by frequency (descending)
pairs.sort((a, b) -> b[1] - a[1]);
// Step 4: Take top k
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = pairs.get(i)[0];
}
return result;
}
}
⏰ Time: O(n log n) - Sorting dominates
💾 Space: O(n) - HashMap + List
Why This Works but is Slow:
✓ Simple and straightforward
✓ Easy to code and understand
✓ Handles all cases correctly
✗ O(n log n) doesn't meet follow-up requirement
✗ Sorting entire list when we only need k elements
✗ Wasteful when k << unique elements
💡 The First AHA Moment
PROBLEM ANALYSIS:
"I'm sorting ALL elements by frequency"
"But I only need TOP K!"
This is EXACTLY like "Kth Largest Element" problem!
INSIGHT:
"Don't need full sort for top K!"
"Use HEAP to track top K efficiently!"
Similar to Problem 275 (Kth Largest):
- That used max-heap
- This uses min-heap of size k
Keep k most frequent elements in heap
Min-heap makes evicting least frequent easy!
TIME IMPROVEMENT:
Full sort: O(n log n)
Min-heap: O(n log k)
When k << n, MUCH better!
Example: n=10000, k=10 → 10000×log(10) vs 10000×log(10000)
🎯 Approach 2: Min-Heap of Size K ⭐⭐
The Better Solution
The Evolution of Thought:
Brute Force: Sort all → Take k
⬇
Question: "Do I need FULL sort for just k elements?"
⬇
Answer: "NO! Use min-heap like in Kth Largest!"
⬇
Better Idea: "Keep heap of size k with k most frequent!"
WHY Min-Heap and Not Max-Heap? - Critical Reasoning
The Core Question:
We want TOP K most frequent elements.
Should we use Min-Heap or Max-Heap? Why?
Answer Through Reasoning:
APPROACH 1: Max-Heap (seems natural?)
═══════════════════════════════════════════════════════════════
Max-heap keeps LARGEST on top.
If we use max-heap:
- Add all elements to heap
- Poll k times to get top k
Code:
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>((a, b) -> freqMap.get(b) - freqMap.get(a));
for (int num : freqMap.keySet()) {
maxHeap.offer(num); // Add all
}
for (int i = 0; i < k; i++) {
result[i] = maxHeap.poll(); // Get top k
}
Analysis:
- Add n unique elements: O(n log n)
- Poll k elements: O(k log n)
- Total: O(n log n)
Problem: STILL O(n log n)! ✗
Not better than sorting!
═══════════════════════════════════════════════════════════════
APPROACH 2: Min-Heap of Size K (smart!)
═══════════════════════════════════════════════════════════════
Min-heap keeps SMALLEST on top.
Strategy:
- Maintain heap of ONLY k elements
- Heap contains k MOST frequent
- Min on top = LEAST frequent among top k
- Easy to evict when found more frequent!
Why this works:
If heap has k elements and we find element with higher freq:
- Current min freq in heap = least frequent of top k
- New element has higher freq
- Remove min (least of top k)
- Add new element
- Heap still has k most frequent!
Code:
PriorityQueue<Integer> minHeap =
new PriorityQueue<>((a, b) -> freqMap.get(a) - freqMap.get(b));
for (int num : freqMap.keySet()) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // Remove least frequent
}
}
Analysis:
- Process n unique elements
- Each offer: O(log k)
- Each poll: O(log k)
- Total: O(n log k)
When k << n: MUCH better! ✓
Example: k=10, n=10000 → log(10) << log(10000)
═══════════════════════════════════════════════════════════════
WHY MIN-HEAP WINS:
═══════════════════════════════════════════════════════════════
Key Difference:
Max-heap: Must add ALL elements → O(n log n)
Min-heap: Maintain ONLY k elements → O(n log k)
The Insight:
We DON'T need all elements sorted!
We ONLY need top k!
Min-heap of size k gives us:
- k most frequent elements (in heap)
- Easy eviction (poll removes least of top k)
- O(log k) operations, not O(log n)!
This is the SAME pattern as Problem 275 (Kth Largest)! ✨
Visual Tracking - Complete Example
Input: nums = [1,1,1,2,2,3,4,4,4,4], k = 2
Step 1: Count frequencies
freqMap = {1: 3, 2: 2, 3: 1, 4: 4}
Step 2: Build min-heap of size k=2
═══════════════════════════════════════════════════════════════
Process element 1 (freq=3)
═══════════════════════════════════════════════════════════════
Heap: []
Add 1 (freq=3)
Heap: [1]
↑
freq=3
Size: 1 ≤ k=2 → Keep it
═══════════════════════════════════════════════════════════════
Process element 2 (freq=2)
═══════════════════════════════════════════════════════════════
Heap: [1]
Add 2 (freq=2)
Heap: [2, 1] (min-heap, 2 has lower freq)
↑
freq=2 (min)
Size: 2 = k → Heap full now!
═══════════════════════════════════════════════════════════════
Process element 3 (freq=1)
═══════════════════════════════════════════════════════════════
Heap: [2, 1]
min=2 (freq=2)
Compare: 3 (freq=1) vs min (freq=2)
1 < 2? YES → 3 is LESS frequent than min in heap
Decision: SKIP 3!
WHY?
Heap has [2, 1] with freq [2, 3]
These are top 2 so far
Element 3 with freq=1 is less frequent
→ Not in top k
→ Don't add it
Heap: [2, 1] (unchanged)
═══════════════════════════════════════════════════════════════
Process element 4 (freq=4)
═══════════════════════════════════════════════════════════════
Heap: [2, 1]
min=2 (freq=2)
Compare: 4 (freq=4) vs min (freq=2)
4 > 2? YES → 4 is MORE frequent than min in heap!
Decision: REPLACE min with 4!
WHY?
Current heap: [2, 1] with freq [2, 3]
Element 4 has freq=4
4 is more frequent than 2 (current min)
→ 4 should be in top k
→ Remove 2 (least of current top k)
→ Add 4
Step 1: Remove min
heap.poll() removes 2
Heap: [1]
Step 2: Add 4
heap.offer(4)
Heap: [1, 4] (min-heap adjusts)
Actually: [1, 4] where 1 has freq=3, 4 has freq=4
Min-heap by frequency: [1, 4]
↑
freq=3 (smaller)
Heap: [1, 4]
↑
min (freq=3)
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
Final heap: [1, 4]
Elements with frequencies:
1 → freq=3
4 → freq=4
These are the top 2 most frequent! ✓
Result: [1, 4] or [4, 1] (order doesn't matter)
Verification:
4 appears 4 times ← most frequent ✓
1 appears 3 times ← 2nd most frequent ✓
2 appears 2 times ← not in top 2
3 appears 1 time ← not in top 2
Implementation
import java.util.*;
/**
* Min-Heap of size k
* Time: O(n log k)
* Space: O(n)
*/
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// Step 1: Count frequencies
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// Step 2: Min-heap by frequency (smallest freq on top)
PriorityQueue<Integer> minHeap = new PriorityQueue<>(
(a, b) -> freqMap.get(a) - freqMap.get(b)
);
// Step 3: Maintain heap of size k
for (int num : freqMap.keySet()) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // Remove least frequent
}
}
// Step 4: Extract result
int[] result = new int[k];
for (int i = 0; i < k; i++) {
result[i] = minHeap.poll();
}
return result;
}
}
⏰ Time: O(n log k) - Much better when k << n
💾 Space: O(n) - HashMap + heap of size k
Why This is Better:
✓ O(n log k) vs O(n log n) when k << n
✓ Only maintains k elements in heap
✓ Efficient eviction with min-heap
Example improvement:
n = 10,000, k = 10
Sorting: 10,000 × log(10,000) ≈ 130,000 ops
Min-heap: 10,000 × log(10) ≈ 33,000 ops
4x faster! ✨
But... follow-up wants O(n)!
Can we do even better?
💡 The Second AHA Moment
PROBLEM ANALYSIS:
Min-heap is O(n log k), better than O(n log n).
But follow-up wants O(n)!
Can we eliminate the log factor?
OBSERVATION:
"Frequency values are BOUNDED!"
"Max frequency = n (all elements same)"
"Min frequency = 1"
"Frequency range: [1, n]"
What if we use this bounded range?
INSIGHT:
"Create BUCKETS by frequency!"
Bucket sort! ✨
Bucket[i] = list of elements with frequency i
bucket[0] = [] (no element has freq 0)
bucket[1] = [elements with freq 1]
bucket[2] = [elements with freq 2]
...
bucket[n] = [elements with freq n]
Then collect from high frequency to low!
TIME: O(n) to create buckets + O(n) to collect = O(n)! ✓
This is BUCKET SORT - perfect when values are bounded! 🎯
🎯 Approach 3: Bucket Sort (Optimal) ⭐⭐⭐
The Optimal Solution
The Evolution of Thought:
Brute Force: Sort all
⬇
Min-Heap: Keep top k
⬇
Question: "Can we eliminate log factor?"
⬇
Observation: "Frequency is bounded [1, n]!"
⬇
Answer: "Use bucket sort by frequency!"
⬇
Optimal: O(n) time - meets follow-up! ✨
Understanding Bucket Sort - Complete Explanation
What is Bucket Sort?
BUCKET SORT CONCEPT:
Normal sort: Compare elements → O(n log n)
Bucket sort: Use value as index → O(n)!
When to use:
✓ Values are integers
✓ Value range is bounded and known
✓ Can create array of size (max - min + 1)
In our problem:
- Values: frequencies (how often element appears)
- Range: [1, n] where n = array length
- Can create: array of size n+1 (indices 0 to n)
Strategy:
1. Count frequencies (HashMap)
2. Create buckets by frequency
3. Collect from high to low frequency
WHY Bucket Sort Works Here - Critical Reasoning
The Core Question:
Why can we use bucket sort?
What makes frequency special?
Answer Through Reasoning:
REQUIREMENT FOR BUCKET SORT:
═══════════════════════════════════════════════════════════════
Bucket sort needs:
1. Integer values
2. Known bounded range
3. Can afford array of that size
For frequencies:
1. Frequencies are integers ✓
(element appears 1, 2, 3... times)
2. Range is [1, n] ✓
Proof:
Min frequency: 1 (element appears at least once)
Max frequency: n (all elements are same)
Example: [5,5,5,5] → 5 appears 4 times (n=4)
3. Array of size n+1 is affordable ✓
n ≤ 10^5 (from constraints)
Creating array of size 10^5 is fine!
So we CAN use bucket sort! ✓
═══════════════════════════════════════════════════════════════
HOW BUCKET SORT GIVES O(n):
═══════════════════════════════════════════════════════════════
Step 1: Count frequencies
Time: O(n) - scan array once
Step 2: Create buckets
For each unique element:
Add to bucket[frequency]
Time: O(unique elements) ≤ O(n)
Step 3: Collect top k
Scan buckets from high to low
Time: O(n) - at most n buckets
Stop when collected k elements
Total: O(n) + O(n) + O(n) = O(n) ✓
═══════════════════════════════════════════════════════════════
WHY WE SCAN FROM HIGH TO LOW:
═══════════════════════════════════════════════════════════════
We want TOP k most frequent.
Bucket[i] contains elements with frequency i.
High frequency = more frequent
Low frequency = less frequent
To get most frequent first:
Start from bucket[n] (highest possible frequency)
Go down to bucket[1] (lowest frequency)
Stop when collected k elements
Example:
n = 6
bucket[6] = []
bucket[5] = []
bucket[4] = [5] ← Start here (highest with elements)
bucket[3] = [1] ← Then here
bucket[2] = [2,6] ← Then here if needed
bucket[1] = [3,4]
If k=2: Take from bucket[4] and bucket[3] → [5, 1] ✓
Most frequent collected first!
Visual Tracking - Complete Example
Input: nums = [1,1,1,2,2,3], k = 2
═══════════════════════════════════════════════════════════════
STEP 1: Count Frequencies
═══════════════════════════════════════════════════════════════
Scan array:
1 appears 3 times
2 appears 2 times
3 appears 1 time
freqMap = {1: 3, 2: 2, 3: 1}
═══════════════════════════════════════════════════════════════
STEP 2: Create Buckets by Frequency
═══════════════════════════════════════════════════════════════
n = 6 (array length)
Create buckets array of size n+1 (indices 0 to 6)
buckets = [[], [], [], [], [], [], []]
0 1 2 3 4 5 6
↑
freq (index)
For each element in freqMap:
Element 1 has freq=3 → Add to bucket[3]
Element 2 has freq=2 → Add to bucket[2]
Element 3 has freq=1 → Add to bucket[1]
After placing:
buckets[0] = [] (no element has freq 0)
buckets[1] = [3] (element 3 appears 1 time)
buckets[2] = [2] (element 2 appears 2 times)
buckets[3] = [1] (element 1 appears 3 times)
buckets[4] = [] (no element has freq 4)
buckets[5] = [] (no element has freq 5)
buckets[6] = [] (no element has freq 6)
Visual:
freq 6: []
freq 5: []
freq 4: []
freq 3: [1] ← Highest frequency with elements
freq 2: [2]
freq 1: [3] ← Lowest frequency
freq 0: []
═══════════════════════════════════════════════════════════════
STEP 3: Collect Top K from High to Low Frequency
═══════════════════════════════════════════════════════════════
k = 2 (need 2 elements)
result = []
Scan from freq=6 down to freq=1:
Check freq=6: bucket[6] = []
Empty, continue
Check freq=5: bucket[5] = []
Empty, continue
Check freq=4: bucket[4] = []
Empty, continue
Check freq=3: bucket[3] = [1]
Has elements!
Add 1 to result
result = [1]
count = 1 (need 1 more)
Check freq=2: bucket[2] = [2]
Has elements!
Add 2 to result
result = [1, 2]
count = 2 (reached k!) ← STOP
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
result = [1, 2]
Top 2 most frequent elements: [1, 2] ✓
Verification:
1 appears 3 times ← most frequent ✓
2 appears 2 times ← 2nd most frequent ✓
3 appears 1 time ← not in top 2
Time complexity: O(n) ✓
Meets follow-up requirement!
Another Example - Multiple Elements per Bucket
Input: nums = [4,1,-1,2,-1,2,3], k = 2
═══════════════════════════════════════════════════════════════
STEP 1: Count Frequencies
═══════════════════════════════════════════════════════════════
freqMap = {4: 1, 1: 1, -1: 2, 2: 2, 3: 1}
═══════════════════════════════════════════════════════════════
STEP 2: Create Buckets
═══════════════════════════════════════════════════════════════
n = 7
buckets[0] = []
buckets[1] = [4, 1, 3] ← Multiple elements with freq=1
buckets[2] = [-1, 2] ← Multiple elements with freq=2
buckets[3] = []
buckets[4] = []
buckets[5] = []
buckets[6] = []
buckets[7] = []
Note: Multiple elements can have SAME frequency!
That's why each bucket is a LIST!
═══════════════════════════════════════════════════════════════
STEP 3: Collect Top K
═══════════════════════════════════════════════════════════════
k = 2
Scan from high to low:
Check freq=7 to freq=3: All empty
Check freq=2: bucket[2] = [-1, 2]
Has 2 elements!
Add both: result = [-1, 2]
count = 2 (reached k!) ← STOP
═══════════════════════════════════════════════════════════════
RESULT
═══════════════════════════════════════════════════════════════
result = [-1, 2]
Both appear 2 times (tied for most frequent) ✓
Note: We could also return [2, -1] - order doesn't matter!
Implementation
import java.util.*;
/**
* Bucket Sort (Optimal)
* Time: O(n)
* Space: O(n)
*/
class Solution {
public int[] topKFrequent(int[] nums, int k) {
// Step 1: Count frequencies
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// Step 2: Create buckets by frequency
// buckets[i] = list of elements with frequency i
List<Integer>[] buckets = new List[nums.length + 1];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
for (int num : freqMap.keySet()) {
int freq = freqMap.get(num);
buckets[freq].add(num);
}
// Step 3: Collect top k from high frequency to low
int[] result = new int[k];
int index = 0;
for (int freq = buckets.length - 1; freq >= 0 && index < k; freq--) {
for (int num : buckets[freq]) {
result[index++] = num;
if (index == k) {
return result;
}
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(Arrays.toString(sol.topKFrequent(new int[]{1,1,1,2,2,3}, 2))); // [1, 2]
System.out.println(Arrays.toString(sol.topKFrequent(new int[]{1}, 1))); // [1]
}
}
⏰ Time: O(n) - Meets follow-up requirement!
💾 Space: O(n) - HashMap + buckets array
Why This is Optimal:
✓ O(n) time - can't do better (must scan array)
✓ Meets follow-up requirement
✓ Simple and elegant
✓ No sorting, no heap overhead
✓ Perfect for bounded frequency values
Comparison:
Sorting: O(n log n)
Min-heap: O(n log k)
Bucket sort: O(n) ← BEST! ✨
📊 Approach Comparison - The Complete Growth Journey
┌──────────────┬─────────────┬──────────┬──────────────────────┐
│ Approach │ Time │ Space │ Key Insight │
├──────────────┼─────────────┼──────────┼──────────────────────┤
│ Sorting │ O(n log n) │ O(n) │ Sort by frequency │
│ Min-Heap │ O(n log k) │ O(n) │ Keep top k only │
│ Bucket Sort │ O(n) │ O(n) │ Frequency bounded │
└──────────────┴─────────────┴──────────┴──────────────────────┘
THE COMPLETE LEARNING PROGRESSION:
Level 1: Brute Force (Sorting)
Thought: "Count frequencies → Sort → Take k"
Works? YES ✓
Optimal? NO ✗
Time: O(n log n)
Problem: Doesn't meet follow-up
Level 2: Optimization Insight #1
Question: "Do I need FULL sort for k elements?"
Realization: "Same as Kth Largest problem!"
Idea: "Use min-heap of size k!"
Level 3: Min-Heap Solution
Implementation: Min-heap tracks k most frequent
Result: O(n log k)
Better: Much better when k << n ✓
Example: k=10, n=10000 → 4x faster!
But: Still has log factor
Level 4: Optimization Insight #2
Question: "Can we eliminate log factor?"
Realization: "Frequency is bounded [1, n]!"
Idea: "Use bucket sort by frequency!"
Level 5: Bucket Sort (Optimal)
Implementation: Buckets by frequency
Result: O(n) time ✓
Perfect: Meets follow-up requirement! ✨
Growth: Learned when to use bucket sort!
CONCRETE EXAMPLE (n=10,000, k=10):
Sorting:
Sort 10,000 elements
Time: 10,000 × log(10,000) ≈ 130,000 ops
Min-Heap:
Process 10,000, maintain heap of 10
Time: 10,000 × log(10) ≈ 33,000 ops
4x FASTER than sorting! 🚀
Bucket Sort:
Count + create buckets + collect
Time: 10,000 + 10,000 + 10,000 = 30,000 ops
Slightly better than heap! ✨
For large k:
If k = 5,000:
Min-heap: 10,000 × log(5,000) ≈ 120,000 ops
Bucket: Still 30,000 ops
Bucket MUCH better! 🎯
💡 Key Learnings - Your Complete Growth
WHAT YOU LEARNED:
1. PROBLEM PATTERN RECOGNITION:
✓ "Top K" problems → Think heap!
✓ Similar to Problem 275 (Kth Largest)
✓ Min-heap for "top k" items
2. WHY MIN-HEAP NOT MAX-HEAP:
✓ Min-heap of size k: O(n log k)
✓ Max-heap with all: O(n log n)
✓ Size matters for complexity!
3. BUCKET SORT APPLICABILITY:
✓ When values are bounded integers
✓ Can create array of that size
✓ Achieves O(n) without comparison!
4. SPACE-TIME TRADE-OFF:
✓ All approaches use O(n) space
✓ But time improves significantly
✓ Bucket sort uses frequency bounds
5. FOLLOW-UP QUESTIONS:
✓ "Better than O(n log n)" → Think O(n)
✓ Bounded values → Bucket sort!
✓ Know multiple approaches!
INTERVIEW STRATEGY:
Progressive Presentation:
"I can solve this in three ways:
Approach 1: Sort by frequency O(n log n)
Simple but doesn't meet follow-up.
Approach 2: Min-heap of size k O(n log k)
Better when k << n. Like Kth Largest problem.
Keep k most frequent, evict least frequent.
Approach 3: Bucket sort O(n)
Frequency bounded [1,n]. Create buckets.
Collect from high to low. Meets follow-up!
Let me implement bucket sort for O(n)."
Shows:
✓ Multiple solution awareness
✓ Complexity analysis
✓ Pattern recognition
✓ Optimal solution knowledge
This is REAL mastery! 🌱→🌳→🌲→🏆
⚠️ Common Mistakes
Mistake 1: Using max-heap with all elements
// ❌ WRONG - O(n log n), same as sorting!
PriorityQueue<Integer> maxHeap =
new PriorityQueue<>((a,b) -> freqMap.get(b) - freqMap.get(a));
for (int num : freqMap.keySet()) {
maxHeap.offer(num); // Add all
}
// ✓ CORRECT - Min-heap of size k: O(n log k)
PriorityQueue<Integer> minHeap =
new PriorityQueue<>((a,b) -> freqMap.get(a) - freqMap.get(b));
for (int num : freqMap.keySet()) {
minHeap.offer(num);
if (minHeap.size() > k) {
minHeap.poll(); // Keep only k
}
}
Mistake 2: Wrong bucket size
// ❌ WRONG - Size should be n+1, not unique elements
List<Integer>[] buckets = new List[freqMap.size()];
// ✓ CORRECT - Bucket index is frequency (max = n)
List<Integer>[] buckets = new List[nums.length + 1];
Mistake 3: Wrong scan direction in bucket sort
// ❌ WRONG - Scanning from low to high frequency
for (int freq = 0; freq < buckets.length; freq++) {
// Gets least frequent first!
}
// ✓ CORRECT - Scan from high to low frequency
for (int freq = buckets.length - 1; freq >= 0; freq--) {
// Gets most frequent first!
}
Mistake 4: Not initializing bucket lists
// ❌ WRONG - NullPointerException!
List<Integer>[] buckets = new List[nums.length + 1];
buckets[freq].add(num); // NPE!
// ✓ CORRECT - Initialize each bucket
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
🎯 Pattern Recognition
Problem Type: Top K Selection by Frequency
Core Patterns: Heap + Bucket Sort
When to Apply:
✓ "Top k" or "most/least frequent"
✓ Need k elements by some criteria
✓ Frequency/count based selection
✓ Can use bounded value optimization
Recognition Keywords:
- "top k"
- "most frequent"
- "k most/least"
- "highest/lowest frequency"
Similar Problems:
- Kth Largest Element (LC 215) - Min-heap pattern
- Top K Frequent Words (LC 692) - Same pattern + trie
- Sort Characters by Frequency (LC 451) - Bucket sort
- K Closest Points (LC 973) - Min-heap for top k
Key Components:
┌────────────────────────────────────────────┐
│ Frequency Map: Count occurrences │
│ Min-Heap: Keep top k (when k << n) │
│ Bucket Sort: When values bounded (O(n)) │
│ Choose based on: k size and constraints │
└────────────────────────────────────────────┘
📝 Quick Revision Notes
🎯 Core Concept:
Find k most frequent elements. Brute force: Count → sort by frequency O(n log n). Better: Min-heap of size k keeps k most frequent, evict least O(n log k). Optimal: Bucket sort - frequency bounded [1,n], create buckets, collect high→low O(n). Follow-up satisfied!
⚡ Quick Implementations:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.PriorityQueue;
public class Solution {
public int[] topKFrequent(int[] a, int k) {
// return naive(a, k);
// return minHeap(a, k);
return bucketSort(a, k);
}
private int[] bucketSort(int[] a, int k) {
int[] res = new int[k];
// step 1: freq map
HashMap<Integer, Integer> freqMap = new HashMap<>();
for (int num : a) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// step 2: create a bucket array of size a.length + 1 where
// bucket[i] stores the elements having frequency i.
// why size a.length? if there is only 1 element that gets repeated
// in whole array, for example, 5 times, then bucket[5] = {1}
// Its an array whose element is a List.
// int[] => array of integers => new int[]
// List[] => array of lists => new ArrayList[]
// For example, for [1, 2, 1, 2, 1, 2, 3, 1, 3, 2] which has
// freqMap of {1:4, 2:4, 3:2}. bucket[0...10] will be created.
// bucket[0], bucket[1] bucket[3] => empty list
// bucket[2] => {3}
// bucket[4] => {1,4}
// bucket[5] to bucket[10] => again empty lists
int size = a.length;
List<Integer>[] bucket = new ArrayList[size + 1];
// initialize
for (int i = 0; i <= size; i++) {
bucket[i] = new ArrayList<>();
}
for (int key : freqMap.keySet()) {
bucket[freqMap.get(key)].add(key);
}
// step 3: loop through the bucket array from last to first as
// index indicates frequency and we need top k frequent elements
int count = 0;
for (int i = size; i >= 0; i--) {
for (int num : bucket[i]) {
if (count == k) {
return res;
}
res[count] = num;
count++;
}
}
return res;
}
private int[] minHeap(int[] a, int k) {
int[] res = new int[k];
// step 1: freq map
HashMap<Integer, Integer> freqMap = new HashMap<>();
for (int num : a) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// step 2: add to PQ instead of list for sorting based on freq later
// ArrayList<int[]> freqList = new ArrayList<>();
PriorityQueue<int[]> pq = new PriorityQueue<>((a1, a2) -> a2[1] - a1[1]);
for (int key : freqMap.keySet()) {
pq.offer(new int[] { key, freqMap.get(key) });
}
// step 3: put in res array
for (int i = 0; i < k; i++) {
res[i] = pq.poll()[0];
}
return res;
}
private int[] naive(int[] a, int k) {
int[] res = new int[k];
// step 1: freq map
HashMap<Integer, Integer> freqMap = new HashMap<>();
for (int num : a) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// step 2: convert to list for sorting based on freq later
ArrayList<int[]> freqList = new ArrayList<>();
for (int key : freqMap.keySet()) {
freqList.add(new int[] { key, freqMap.get(key) });
}
// step 3: sort the freq array based on freq in desc order
Collections.sort(freqList, (a1, a2) -> a2[1] - a1[1]);
// step 4: put in res array
for (int i = 0; i < k; i++) {
res[i] = freqList.get(i)[0];
}
return res;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(Arrays.toString(s.topKFrequent(new int[] { 1, 1, 1, 2, 2, 3 }, 2))); // [1,2]
System.out.println(Arrays.toString(s.topKFrequent(new int[] { 1, 2, 1, 2, 1, 2, 3, 1, 3, 2 }, 2))); // [1,2]
}
}
🔑 Key Insights:
- Natural Progression: Sort → Min-heap → Bucket sort
- Min-Heap Why: Keep ONLY k elements vs all elements
- Min Not Max: Size k gives O(n log k) not O(n log n)
- Bucket Sort When: Bounded integer values [1, n]
- Scan Direction: High→low frequency for most frequent first
- Multiple per Bucket: Same frequency = multiple elements in bucket
- Growth: O(n log n) → O(n log k) → O(n)! ✓
🎪 Memory Aid:
"Count → Min-heap of k → Bucket by frequency!"
"Min-heap keeps k, not all!"
"Bounded values → Bucket sort wins!" ✨
🧪 Edge Cases
Case 1: k = 1
Input: [1,1,1,2,2,3], k = 1
Output: [1]
Most frequent only
Case 2: k = unique elements
Input: [1,2,3], k = 3
Output: [1,2,3] (any order)
All elements have same frequency
Case 3: Single element
Input: [1], k = 1
Output: [1]
Case 4: Tied frequencies
Input: [1,1,2,2], k = 2
Output: [1,2]
Both have same freq, both included
All handled correctly! ✓
🎓 Complexity Analysis
Approach 1: Sorting
Time: O(n log n)
Count: O(n)
Sort: O(u log u) where u = unique ≤ n
Overall: O(n log n)
Space: O(n)
HashMap + list
Approach 2: Min-Heap
Time: O(n log k)
Count: O(n)
Heap ops: u elements × O(log k) = O(n log k)
Extract: k × O(log k) = O(k log k)
Overall: O(n log k)
Space: O(n)
HashMap + heap of size k
Approach 3: Bucket Sort
Time: O(n)
Count: O(n)
Create buckets: O(u) ≤ O(n)
Collect: O(n) worst case
Overall: O(n) ✓
Space: O(n)
HashMap + buckets array
Optimal! Meets follow-up!
Happy practicing! 🎯
Note: This problem is a MASTERCLASS in "Top K" optimization! You naturally start with sorting (easy but O(n log n)), realize min-heap is better for top k (O(n log k)), then discover bucket sort when values are bounded (O(n)). The progression teaches three critical patterns: (1) Min-heap for top k when k << n, (2) Why min-heap not max-heap (size matters!), (3) Bucket sort for bounded integer values. Understanding WHY we advance certain pointers, WHY min-heap over max-heap, and WHY bucket sort works here builds deep algorithmic intuition! True growth! 💪✨🏆