347. Top K Frequent Elements
Asked at Amazon, Apple, Microsoft, Netflix and 6 more
Difficulty
Medium
Time
O(n)
Space
O(n)
Pattern
Array
Companies
10
Problem
You are given an integer array nums and an integer k. Return the k values that appear most often in the array.
The order of the returned values does not matter. The answer is guaranteed to be unique, so there is no tie to break.
A simple way is to count how many times each value appears, then pick the k values with the largest counts. To do better than sorting, think about the fact that a count can only be between 1 and n. You can use the count itself as an array index.
Count each value, then take the top k
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] - ●
The answer is guaranteed to be unique
Examples
nums = [1,1,1,2,2,3], k = 2[1,2]nums = [1], k = 1[1]nums = [1,2,1,2,1,2,3,1,3,2], k = 2[1,2]Asked At
10 companies| 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 → |
| Visa | Medium | View all Visa questions → |
| Snowflake | Medium | View all Snowflake questions → |
| NVIDIA | Medium | View all NVIDIA 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.
When to use which: if k is small relative to n, min-heap is good (O(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.
Bucket sort by frequency
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
O(n) timefrom 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 runs in O(n) time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Top K Frequent Elements?
Top K Frequent Elements is asked at Amazon, Apple, Microsoft, Netflix, Atlassian, Rippling, Walmart, Visa, Snowflake, NVIDIA. 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.