MediumArrayHash TableDivide and ConquerSortingHeap (Priority Queue)Bucket SortCountingQuickselect·AmazonGoogleMeta
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⁵
-10⁴ ≤ nums[i] ≤ 10⁴
k is in the range [1, the number of unique elements in nums]
It is guaranteed that the answer is unique.
Hints
Hint 1Start by counting how often each element appears.▼
First build a frequency map: iterate through nums and count occurrences of each element using a hash map. This takes O(n) time and gives you a count dictionary mapping each element to its frequency.
Hint 2Sorting by frequency is O(n log n) — can you do better?▼
The obvious approach is to sort the count map by value and take the top k — but that's O(n log n). Notice that no element can appear more than n times, so frequencies are bounded by [1, n]. This bound enables sorting without comparison!
Hint 3Use bucket sort indexed by frequency.▼
Create an array freq of n+1 empty lists. For each element, place it in freq[count[element]]. Then scan freq from right (highest freq) to left, collecting elements until you have k. Total: O(n) time and space.
Brute Force Approach
O(n log n) Time
🔄
Count Then Sort
Time O(n log n)Space O(n)
Count each element's frequency with a hash map, then sort the unique elements by frequency descending and return the first k.
1Build a frequency map in O(n).
2Sort the map keys by frequency in descending order — O(u log u) where u ≤ n unique elements.
3Return the first k elements. Simple but not strictly O(n).
deftopKFrequent(nums, k):
count =
for n in nums:
count[n] = count.get(n, 0) + 1returnsorted(count, key=lambda x: -count[x])[:k]
Optimal Approach — Bucket Sort
O(n) Time
🪣
Linear Time Bucketing
Time O(n)Space O(n)
While a Max Heap takes exactly O(k log n) time, we can optimize to strictly O(n) time using Bucket Sort! Because the frequency of any element cannot exceed the length of the array itself, we can build a bounded array of "frequency buckets".
1Build a Hash Map counting the occurrences of each element.
2Initialize an array of empty lists freq of size len(nums) + 1. The index represents the frequency!
3Iterate through the Hash Map, dropping elements into freq[count[element]].
4Scan freq linearly backwards from right (highest frequency) to left (lowest), gathering elements until we hit k.
READYPress ▶ or step forward to begin.
✓
—
Executing Code
deftopKFrequent(nums, k):
count, freq, res = , [[] for i inrange(len(nums) + 1)], []
for n in nums:
count[n] = 1 + count.get(n, 0)
for n, c in count.items():
freq[c].append(n)
for i inrange(len(freq) - 1, 0, -1):
for n in freq[i]:
res.append(n)
iflen(res) == k:
return res
Time Complexity Analysis
Pass 1 — CountO(n)One full scan through nums to build the frequency hash map. Each increment is O(1) average.
Pass 2 — Fill bucketsO(n)Iterate the count map (at most n unique elements) and place each into its frequency bucket. The bucket array has exactly n + 1 slots — bounded by array length, not infinity.
Pass 3 — Harvest top kO(n)Scan bucket array right-to-left. We touch at most n slots total and stop as soon as we collect k elements — often much earlier in practice.
TotalO(n)Three independent O(n) passes. Space is O(n) for the count map and the bucket array.
vs. Heap approach: A max-heap gives O(n) to build then O(k log n) to extract k elements. For small k this can be fast in practice, but bucket sort beats it asymptotically and requires simpler code — no comparator needed.
Discussion
…