How would you find the top K elements in an array?
Three approaches: (a) sort and slice — O(n log n), simplest, fine for small n; (b) min-heap of size k — O(n log k), best when n ≫ k; (c) Quickselect — O(n) average, O(n²) worst, in-place. Pick by data size + whether you need elements in sorted order.
(a) Sort then slice
function topK(arr, k) {
return [...arr].sort((a, b) => b - a).slice(0, k);
}O(n log n) time, O(n) space. Simple, idiomatic, and the right choice for n ≤ 10k or when readability dominates.
(b) Min-heap of size k
Maintain a heap of the k largest seen so far. The heap's min is the threshold; anything smaller is ignored.
function topK(arr, k) {
const heap = []; // tiny min-heap
const push = (v) => {
heap.push(v);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length) {
heap[0] = last;
let i = 0;
while (true) {
const l = i * 2 + 1, r = i * 2 + 2;
let s = i;
if (l < heap.length && heap[l] < heap[s]) s = l;
if (r < heap.length && heap[r] < heap[s]) s = r;
if (s === i) break;
[heap[i], heap[s]] = [heap[s], heap[i]];
i = s;
}
return top;
}
};
for (const v of arr) {
if (heap.length < k) push(v);
else if (v > heap[0]) { pop(); push(v); }
}
return heap.sort((a, b) => b - a);
}O(n log k) time, O(k) space. Beats sort when n ≫ k (e.g., top 10 from 10M).
(c) Quickselect
Partition like quicksort, recurse only into the partition that contains the k-th boundary. Expected O(n), worst O(n²).
function topK(arr, k) {
const a = arr.slice();
function select(left, right, target) {
if (left >= right) return;
const pivot = a[right];
let i = left;
for (let j = left; j < right; j++) {
if (a[j] > pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }
}
[a[i], a[right]] = [a[right], a[i]];
if (i === target) return;
if (i < target) select(i + 1, right, target);
else select(left, i - 1, target);
}
select(0, a.length - 1, k - 1);
return a.slice(0, k).sort((a, b) => b - a);
}Avoids the log factor entirely, in place. Use median-of-three or random pivot to avoid O(n²) on adversarial inputs.
Pick by context
| Situation | Choose |
|---|---|
| n small, readability matters | Sort + slice |
| n huge, k small (top 10 of 10M) | Min-heap |
| n huge, k ~ n/2, in-place | Quickselect |
| Streaming (don't see all of n) | Min-heap |
| Tied values, stable order required | Sort + slice (stable in JS since ES2019) |
Interview framing
"Three approaches. Sort+slice is O(n log n) and fine for small data — what I'd write first. For n ≫ k I'd use a min-heap of size k: visit each element, keep it if it beats the heap's minimum — O(n log k), O(k) memory. Quickselect is O(n) average and good when you can mutate the array. For streaming input, heap is the only option since sort/quickselect need the full array. Clarify with the interviewer: do we need the top k in sorted order, or just the set?"
Follow-up questions
- •Why is heap better for streaming?
- •What's Quickselect's worst case and how do you mitigate?
- •How would you parallelize this?
Common mistakes
- •Sorting when n is huge and k is small.
- •Quickselect with adversarial pivot strategy.
- •Not handling ties.
Performance considerations
- •Heap is the win for n ≫ k. Sort+slice is most readable and fast enough for most app code. Quickselect avoids the log factor when you can mutate.
Edge cases
- •k > n.
- •Empty array.
- •All equal elements.
- •Non-numeric comparators.
Real-world examples
- •Leaderboards (top 100 of millions), search relevance top-k, ranked product feeds.