Loading…
Top K Frequent Elements is a medium coding interview question covering arrays, heap, hash maps — the kind asked at FAANG (Facebook/Meta, Apple, Amazon, Netflix, Google) and AI-first companies like Anthropic, OpenAI, and Nvidia.
Given an integer array nums and integer k, return the k most frequent elements. The answer can be in any order.
Example: nums=[1,1,1,2,2,3], k=2 -> [1,2]
Target O(n log k) using a heap. Could you achieve O(n) using bucket sort?
Try it yourself first
In an interview you'd get about 25 minutes for a medium question. Sketch an approach before peeking — struggling is where the learning happens.
Stuck? Reveal them one at a time — each hint gives away a little more.
Ready to compare notes? The full solution, visualization, and complexity analysis are below.
Two approaches: a min-heap of size k runs in O(n log k), and bucket sort (frequency buckets 1..n) runs in O(n). The bucket sort is optimal when k is close to n — iterate buckets from highest frequency to collect k elements.
| 1 | import heapq |
| 2 | from collections import Counter |
| 3 | |
| ▶ | def top_k_frequent_heap(nums: list[int], k: int) -> list[int]: |
| ▶ | freq = Counter(nums) |
| 6 | # Min-heap of size k |
| 7 | heap: list[tuple] = [] |
| 8 | for num, cnt in freq.items(): |
| 9 | heapq.heappush(heap, (cnt, num)) |
| 10 | if len(heap) > k: |
| 11 | heapq.heappop(heap) |
| 12 | return [num for _, num in heap] |
| 13 | |
| 14 | def top_k_frequent_bucket(nums: list[int], k: int) -> list[int]: |
| 15 | freq = Counter(nums) |
| 16 | buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)] |
| 17 | for num, cnt in freq.items(): |
| 18 | buckets[cnt].append(num) |
| 19 | result: list[int] = [] |
| 20 | for cnt in range(len(buckets)-1, 0, -1): |
| 21 | result.extend(buckets[cnt]) |
| 22 | if len(result) >= k: |
| 23 | return result[:k] |
| 24 | return result |
Count frequencies: {1:3, 2:2, 3:1}.
Key Insights
A full interview loop is more than one round. These are the others, each with what is on the site for it.