347. Top K Frequent Elements
mediumAsked at TwilioTop K Frequent Elements is Twilio's data-aggregation probe: given an integer array, return the K most frequent values. The grading rubric weighs whether you reach for a min-heap of size K (O(n log K)) or bucket sort (O(n)), and articulate WHY the second is faster when the value range is bounded by n.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Twilio loops.
- Glassdoor (2026-Q1)— Reported in Twilio backend SWE on-site rounds across messaging and analytics teams.
- LeetCode Discuss (2025-12)— Cited in Twilio interview reports as a 'choose-your-data-structure' question.
Problem
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. Your algorithm's time complexity must be better than O(n log n).
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]Example 2
nums = [1], k = 1[1]Approaches
1. Sort by frequency (rejected — violates the O(n log n) constraint)
Count with a map, sort entries by frequency, return the top K.
- Time
- O(n log n)
- Space
- O(n)
function topKFrequentSort(nums, k) {
const counts = new Map();
for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
return [...counts.entries()].sort((a, b) => b[1] - a[1]).slice(0, k).map(e => e[0]);
}Tradeoff: Simplest to write but the problem explicitly forbids O(n log n). Twilio interviewers reject this on the rubric — state it as a baseline then pivot.
2. Min-heap of size K (canonical optimal)
Count with a map, push (freq, val) into a size-K min-heap. Pop when size exceeds K — the heap keeps the K largest.
- Time
- O(n log k)
- Space
- O(n + k)
class MinHeap {
constructor() { this.h = []; }
push(v) {
this.h.push(v);
let i = this.h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.h[p][1] <= this.h[i][1]) break;
[this.h[p], this.h[i]] = [this.h[i], this.h[p]];
i = p;
}
}
pop() {
const top = this.h[0];
const last = this.h.pop();
if (this.h.length > 0) {
this.h[0] = last;
let i = 0; const n = this.h.length;
while (true) {
const l = 2 * i + 1, r = 2 * i + 2;
let s = i;
if (l < n && this.h[l][1] < this.h[s][1]) s = l;
if (r < n && this.h[r][1] < this.h[s][1]) s = r;
if (s === i) break;
[this.h[s], this.h[i]] = [this.h[i], this.h[s]];
i = s;
}
}
return top;
}
size() { return this.h.length; }
}
function topKFrequentHeap(nums, k) {
const counts = new Map();
for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
const heap = new MinHeap();
for (const [val, freq] of counts) {
heap.push([val, freq]);
if (heap.size() > k) heap.pop();
}
const result = [];
while (heap.size() > 0) result.push(heap.pop()[0]);
return result;
}Tradeoff: O(n log k) total — significantly better than O(n log n) when k << n. The heap holds at most K entries at any time, bounding space too.
3. Bucket sort by frequency (asymptotically optimal at O(n))
Frequencies are bounded by n. Bucket entries by frequency, then walk buckets from largest to smallest until K entries are collected.
- Time
- O(n)
- Space
- O(n)
function topKFrequent(nums, k) {
const counts = new Map();
for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
const buckets = Array.from({ length: nums.length + 1 }, () => []);
for (const [val, freq] of counts) buckets[freq].push(val);
const result = [];
for (let f = buckets.length - 1; f >= 0 && result.length < k; f--) {
for (const val of buckets[f]) {
result.push(val);
if (result.length === k) break;
}
}
return result;
}Tradeoff: O(n) time, O(n) space. Wins when k is close to n/2 or you need the absolute best. Doesn't directly extend to a streaming variant (you need n known up front).
Twilio-specific tips
Twilio reviewers grade two things: (1) you propose the trivial sort solution and name why it doesn't satisfy the contract, (2) you offer BOTH the heap and bucket approaches and discuss when each wins. Heap is preferred when k is small and the data is streaming; bucket wins when k is large and the data is bounded. Articulate that bucket sort works specifically because frequencies are bounded by n — that's the key insight grade.
Common mistakes
- Sorting the count map by frequency in a sort step that's O(n log n) — the problem forbids it.
- Using a MAX heap and pulling K times — that's O(n + k log n) which is fine for K small but loses to bucket sort.
- Forgetting that buckets must be indexed by frequency (which can be 1..n), not by value.
Follow-up questions
An interviewer at Twilio may pivot to one of these next:
- What if elements arrive as a stream and you can't materialize the array? (LC 692-style — heap with k entries, update counts on the fly.)
- What if you needed the Top-K by SUM of associated weights, not count? (Same shape — replace count with sum in the aggregation pass.)
- How would you parallelize this? (Map-reduce — partition by hash(val), count per partition, then combine with a heap on the reducer.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is bucket sort O(n) and not O(n log n)?
Because we never compare frequencies against each other — we just place each (val, freq) into its bucket in O(1) and walk buckets from the top. The total work is linear in n.
When does heap beat bucket sort?
When the data is streaming (you can't allocate n buckets up front) or when memory is tight. Heap with k entries uses O(k) auxiliary space; bucket uses O(n).
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Top K Frequent Elements and other Twilio interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →