Top K Frequent Elements
Asked at Amazon, Apple, Microsoft, Netflix, Atlassian, Rippling, Walmart
Problem
Given an integer array and an integer k, return the k most frequent elements. This problem tests your knowledge of heaps, bucket sort, and when to choose which approach.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Apple | Medium | View all Apple questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Netflix | Medium | View all Netflix questions → |
| Atlassian | Medium | View all Atlassian questions → |
| Rippling | Medium | View all Rippling questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Approach 1 — Sort by frequency: count frequencies, sort by frequency, take top k. O(n log n). Works but not optimal.
Approach 2 — Min-heap of size k: count frequencies, maintain a min-heap of size k. For each element, if heap size < k, push. If frequency > heap min, pop and push. O(n log k). Better for small k.
Approach 3 — Bucket sort (optimal): count frequencies, create buckets where index = frequency. Place each element in its frequency bucket. Collect from highest bucket down until k elements. O(n) time.
Why bucket sort works: frequencies range from 1 to n. Create n+1 buckets. Bucket[3] contains all elements that appear 3 times. Walk from the highest bucket down, collecting elements until you have k.
Visual walkthrough for [1,1,1,2,2,3], k=2:
Count: {1:3, 2:2, 3:1}
Buckets:
index 0: []
index 1: [3]
index 2: [2]
index 3: [1]
Collect from index 3: [1]. Need 1 more.
Collect from index 2: [1, 2]. Done.
Result: [1, 2]
When to use which: if k is small relative to n, min-heap is good (n log k). If k is close to n, bucket sort is better (O(n)). If you need the kth largest element (not top k), use quickselect O(n) average.
Optimal Approach
Step 1: Count frequencies using a hash map.
Step 2: Create buckets — an array of lists where index = frequency.
Step 3: Place each element in its frequency bucket.
Step 4: Collect from the highest bucket downward until you have k elements.
Bucket sort is optimal because:
- Counting frequencies:
O(n) - Placing in buckets:
O(n) - Collecting from buckets:
O(n) - Total:
O(n)
Time: O(n). Space: O(n) for the hash map and buckets.
What Trips People Up in Real Interviews
Sorting the array and returning the top k. That's O(n log n) and works, but the interviewer expects O(n) using bucket sort or a heap.
Confusing "most frequent" with "largest." The problem asks for the k most frequent elements, not the k largest. Frequency matters, not value.
Using a heap of size n. A min-heap of size k is more efficient: O(n log k) instead of O(n log n). Push elements, and when the heap exceeds k, pop the smallest.
Not handling ties correctly. If multiple elements have the same frequency, any order is acceptable. The problem doesn't specify a tiebreaker.
Creating too many buckets. You need at most n+1 buckets (frequencies range from 1 to n). Creating more wastes space; creating fewer causes index-out-of-bounds.
Solution Code
from collections import Counter
def topKFrequent(nums, k):
count = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, freq in count.items():
buckets[freq].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
for num in buckets[i]:
result.append(num)
if len(result) == k:
return result
return resultFrequently Asked Questions
What is the Top K Frequent Elements problem?
Given an integer array and an integer k, return the k most frequent elements. This problem tests your knowledge of heaps, bucket sort, and when to choose which approach.
How do you solve Top K Frequent Elements?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Top K Frequent Elements?
Top K Frequent Elements is asked at Amazon, Apple, Microsoft, Netflix, Atlassian, Rippling, Walmart. It is a medium difficulty problem.
What are common mistakes on Top K Frequent Elements?
- Sorting the array and returning the top k. That's `O(n log n)` and works, but the interviewer expects `O(n)` using bucket sort or a heap.
- Confusing "most frequent" with "largest." The problem asks for the k most frequent elements, not the k largest. Frequency matters, not value.
- Using a heap of size n. A `min-heap` of size k is more efficient: `O(n log k)` instead of `O(n log n)`. Push elements, and when the heap exceeds k, pop the smallest.
- Not handling ties correctly. If multiple elements have the same frequency, any order is acceptable. The problem doesn't specify a tiebreaker.
- Creating too many buckets. You need at most n+1 buckets (frequencies range from 1 to n). Creating more wastes space; creating fewer causes index-out-of-bounds.