Core Insight Trade one linear scan for a small lookup structure so each value is handled once.
Common Pitfall Do not overwrite information you still need before checking the current value.
Description
Return the k most frequent elements in an array.
Constraints
- Time Complexity:
O(n) - Space Complexity:
O(n)
Tags
arrayhash-mapbucket-sort
Implementation Plan Translate the invariant into these small, testable moves.
- Create the lookup structure.
- Scan each value once.
- Check the needed relationship before updating state.
- Return as soon as the answer is determined.
def topKFrequent(nums, k):
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
freq = [[] for _ in range(len(nums) + 1)]
for num, c in count.items():
freq[c].append(num)
res = []
for i in range(len(freq) - 1, 0, -1):
for num in freq[i]:
res.append(num)
if len(res) == k:
return res