347. Top K Frequent Elements
mediumAsked at DRWDRW asks Top K Frequent Elements to probe heap vs. bucket-sort trade-offs — decisions that matter when ranking the k most-traded instruments by volume or the k most-active order IDs in a session. O(n log k) with a heap is expected; O(n) with bucket sort earns extra credit.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in DRW loops.
- Glassdoor (2026-Q1)— DRW SWE candidates report top-k and heap-based ranking problems as recurring medium-difficulty questions in coding rounds.
- Blind (2025-11)— DRW interview threads note that interviewers specifically ask for the O(n) bucket-sort solution after accepting the heap approach.
Problem
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Constraints
1 <= nums.length <= 10^5−10^4 <= nums[i] <= 10^4k is in the range [1, the number of unique elements in the array].It is guaranteed that the answer is unique.
Examples
Example 1
nums = [1,1,1,2,2,3], k = 2[1,2]Explanation: 1 appears 3 times, 2 appears 2 times — top 2.
Example 2
nums = [1], k = 1[1]Explanation: Single element, k=1.
Approaches
1. Min-heap of size k
Count frequencies with a hash map. Use a min-heap of size k — push each element; if the heap exceeds size k, pop the minimum-frequency element. The heap retains the k most frequent.
- Time
- O(n log k)
- Space
- O(n)
function topKFrequent(nums, k) {
// Count frequencies
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
// Min-heap simulation: sort all unique elements by frequency, take top k
// (JS has no built-in heap; for interview, sort the entries)
const entries = [...freq.entries()]; // [value, count]
entries.sort((a, b) => b[1] - a[1]);
return entries.slice(0, k).map(e => e[0]);
}Tradeoff: O(n log n) as written (sorting all unique elements). For a true O(n log k) solution, implement a min-heap of capacity k. Flag this to the interviewer — explain the heap approach even if the JS sort is what you code.
2. Bucket sort (O(n))
Frequencies range from 1 to n. Create n+1 buckets indexed by frequency. Collect elements from the highest-frequency bucket down until k elements are gathered.
- Time
- O(n)
- Space
- O(n)
function topKFrequent(nums, k) {
const freq = new Map();
for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);
const buckets = Array.from({ length: nums.length + 1 }, () => []);
for (const [val, count] of freq) buckets[count].push(val);
const result = [];
for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
result.push(...buckets[i]);
}
return result.slice(0, k);
}Tradeoff: O(n) time — optimal. Frequency values are bounded by n, so an array of n+1 buckets is sufficient. This is the answer DRW is looking for after you present the heap.
DRW-specific tips
Present both approaches with explicit complexity trade-offs. DRW interviewers expect: 'The heap gives O(n log k) — better than O(n log n) sort when k << n. But if k is close to n, bucket sort is O(n) with no log factor.' They will then ask: 'In a market-data session with 10 million tick events per second and n unique instruments, what is the time budget for computing the top-50 by volume every second?' — the heap approach is bounded by O(n log 50) ≈ O(6n), which is linear and fast enough.
Common mistakes
- Using full sort instead of a heap — O(n log n) versus the O(n log k) the problem implies.
- Bucket array of size n instead of n+1 — frequency n (all elements the same) needs index n.
- Forgetting that multiple elements can share the same frequency bucket — the bucket holds an array, not a single element.
- Off-by-one when collecting from high-frequency buckets — stop when result.length === k.
Follow-up questions
An interviewer at DRW may pivot to one of these next:
- Kth Largest Element in an Array (LC 215) — use QuickSelect for O(n) average.
- Top K Frequent Words (LC 692) — same pattern but with lexicographic tie-breaking.
- How would you maintain the top-k instruments by traded volume in a live stream with O(log k) updates?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is O(n log k) better than O(n log n)?
When k is small (e.g., top 50 out of 10,000 instruments), log k ≈ 6 while log n ≈ 13. The heap approach is roughly twice as fast in this scenario.
Why does the bucket sort work in O(n)?
Frequencies are integers in [1, n]. An array of n+1 buckets is a form of counting sort — O(n) to fill, O(n) to drain. No comparison-based sorting.
How would you handle a live-updating top-k?
Maintain a min-heap of size k. On each update, if the element's frequency exceeds the heap minimum, pop the minimum and push the new element. Each update is O(log k).