Solution 1Bucket Sort
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freq = Counter(nums)
buckets = [[] for _ in range(len(nums))]
for num, count in freq.items():
buckets[count-1].append(num)
output = []
while len(output) != k:
output += buckets.pop()[0: k-len(output)]
return outputpublic int[] topKFrequent2(int[] nums, int k) {
List<List<Integer>> buckets = new ArrayList<>();
for (int i=0; i<=nums.length; i++) {
buckets.add(new ArrayList<>());
}
Map<Integer, Integer> freq = new HashMap<>();
for (int num: nums) {
freq.put(num, freq.getOrDefault(num,0) + 1);
}
for (int num: freq.keySet()) {
int count = freq.get(num);
buckets.get(count).add(num);
}
int[] output = new int[k];
for (int i = buckets.size()-1; i >= 0 ; i--) {
if(buckets.get(i) != null) {
for(int num: buckets.get(i)) {
if (k==0) {
return output;
}
output[k-1] = num;
k--;
}
}
}
return output;
}Solution 2Sort by Freq
- TimeO(n + u log u)
- SpaceO(u)
where, n is len(nums) and u is the number of distinct values.
The first one I reached for.
The log factor never really bites here: values are capped at [-10^4, 10^4], so u <= 20001 and log2(u) <= 15 however big n gets. Counter(nums) is the actual bottleneck and every approach below pays it too.
Pitfalls
[c[n], n] builds a mutable list per entry and for n in c then c[n] hashes every key twice. Swapping both out for sorted(c.items(), key=...) measured 8.17ms -> 3.59ms at n=1e5, u~20k. Same algorithm, same complexity, 2.3x apart
Solved in 9m 40s
class Solution:
'''
Time Complexity: O(n + u log u)
Space Complexity: O(u)
where, n is len(nums) and u is the number of distinct values.
Pitfalls: [c[n], n] builds a mutable list per entry and `for n in c` then `c[n]` hashes every key twice. Swapping both out for sorted(c.items(), key=...) measured 8.17ms -> 3.59ms at n=1e5, u~20k. Same algorithm, same complexity, 2.3x apart.
The first one I reached for.
The log factor never really bites here: values are capped at [-10^4, 10^4], so u <= 20001
and log2(u) <= 15 however big n gets. Counter(nums) is the actual bottleneck and every
approach below pays it too.
'''
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
c = Counter(nums)
l = list(sorted(([c[n],n] for n in c), reverse=True))
return list(l[i][1] for i in range(k))Solution 3Bucket Sort Freq Index
- TimeO(n)
- SpaceO(n)
Intuition said bucket sort before I saw NeetCode's approach list, but I only wrote it after (never read their code).
Index the buckets by frequency instead of comparing frequencies and the log factor disappears. Frequencies are bounded by n, so n+1 buckets covers every possible count and bucket i holds every value seen exactly i times. Popping from the tail walks them in descending frequency order.
n+1 buckets is wasteful though: only max(c.values()) of them can ever fill. Sizing by max(c.values())+1 and building via comprehension instead of an append loop measured
5.58ms -> 1.37ms at n=1e5 with 100 distinct values.
Pitfalls
while len(out) < k has no floor, so it raises IndexError once the buckets run dry, i.e. whenever k > the number of distinct values. It also overshoots k on ties. LeetCode guarantees neither case, so it passes there. The 2024 [bucket-sort] version above avoids both by slicing [0: k-len(output)]
Solved in 8m 30s
class Solution:
'''
Time Complexity: O(n)
Space Complexity: O(n)
Pitfalls: `while len(out) < k` has no floor, so it raises IndexError once the buckets run dry, i.e. whenever k > the number of distinct values. It also overshoots k on ties. LeetCode guarantees neither case, so it passes there. The 2024 [bucket-sort] version above avoids both by slicing [0: k-len(output)].
Intuition said bucket sort before I saw NeetCode's approach list, but I only wrote
it after (never read their code).
Index the buckets by frequency instead of comparing frequencies and the log factor
disappears. Frequencies are bounded by n, so n+1 buckets covers every possible count
and bucket i holds every value seen exactly i times. Popping from the tail walks them
in descending frequency order.
n+1 buckets is wasteful though: only max(c.values()) of them can ever fill. Sizing by
max(c.values())+1 and building via comprehension instead of an append loop measured
5.58ms -> 1.37ms at n=1e5 with 100 distinct values.
'''
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
c = Counter(nums)
l = []
for _ in range(len(nums)+1):
l.append([])
for num in c:
l[c[num]].append(num)
out = []
while len(out) < k:
out.extend(l.pop(-1))
return outSolution 4Max Heap
- TimeO(n + u + k log u)
- SpaceO(u)
where, n is len(nums), u is the number of distinct values.
The quickest of the three and the cleanest to write.
heapify_max is O(u) and each pop is O(log u), so only the k values actually wanted pay the log. Better than a full sort while k stays small, but the k log u term means it converges on the sort version as k approaches u: measured 3.30ms at k=10 vs 8.76ms at k=u (n=1e5, u~20k), where bucket sort stayed flat at 2.7-2.9ms.
Pitfalls
heapify_max/heappop_max only became public heapq API in Python 3.14. Before that they were the private heapq._heapify_max/_heappop_max, so this is not portable to older runtimes
Solved in 5m 40s
import heapq
class Solution:
'''
Time Complexity: O(n + u + k log u)
Space Complexity: O(u)
where, n is len(nums), u is the number of distinct values.
Pitfalls: heapify_max/heappop_max only became public heapq API in Python 3.14. Before that they were the private heapq._heapify_max/_heappop_max, so this is not portable to older runtimes.
The quickest of the three and the cleanest to write.
heapify_max is O(u) and each pop is O(log u), so only the k values actually wanted
pay the log. Better than a full sort while k stays small, but the k log u term means
it converges on the sort version as k approaches u: measured 3.30ms at k=10 vs 8.76ms
at k=u (n=1e5, u~20k), where bucket sort stayed flat at 2.7-2.9ms.
'''
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
c = Counter(nums)
l = [(freq, num) for num, freq in c.items()]
heapq.heapify_max(l)
out = []
for _ in range(k):
out.append(heapq.heappop_max(l)[1])
return outpublic int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = new PriorityQueue<>(
(a, b) -> b.getValue() - a.getValue()
);
maxHeap.addAll(freq.entrySet());
int[] output = new int[k];
for (int i = 0; i < k; i++) {
output[i] = maxHeap.poll().getKey();
}
return output;
}