Top K elements

Overview

Top K problems ask for the k largest, smallest, most frequent, or closest items. The standard tool is a heap of size k: to keep the k largest, use a min-heap and evict the smallest whenever the heap grows past k. The heap's root is then the kth largest element.

This costs O(n log k) instead of O(n log n) for a full sort, and it works on streams where data never stops. Alternatives include quickselect (O(n) average) and bucket sort when values are bounded, such as frequencies.

When to use it

• Phrases like k largest, k smallest, kth largest, top k frequent, k closest.
• Data arrives as a stream and you must report the current top k.
• n is large and k is small, so sorting everything is wasteful.
• Merging k sorted lists (heap of k list heads).

Problem patterns it solves

Where it is used in real software

Key terms

Min-heap of size k

Keeps the k largest; the root is the kth largest.

Max-heap of size k

Keeps the k smallest; the root is the kth smallest.

Quickselect

Partition-based selection in O(n) average time.

Bucket by frequency

Index an array by count to extract top frequencies in O(n).

Heap of size k

1. 1
   Choose the opposite heap

   For the k largest, use a min-heap (so the weakest of the top k is on top to be evicted).

2. 2
   Push each element

   heap.push(x).

3. 3
   Evict when too big

   If heap.size > k, pop the root.

4. 4
   Read the answer

   The heap holds the top k; the root is the kth largest.

Kth largest with k = 3

nums = [3, 2, 1, 5, 6, 4]

The heap holds the 3 largest values {4, 5, 6}, and its root, 4, is the 3rd largest. Each step is O(log k).

Implementation

1// JavaScript has no built-in heap; this minimal MinHeap is interview-ready2class MinHeap {3  constructor(compare = (a, b) => a - b) { this.data = []; this.compare = compare; }4  get size() { return this.data.length; }5  peek() { return this.data[0]; }6  push(x) {7    const d = this.data;8    d.push(x);9    let i = d.length - 1;10    while (i > 0) {11      const p = (i - 1) >> 1;12      if (this.compare(d[i], d[p]) >= 0) break;13      [d[i], d[p]] = [d[p], d[i]];14      i = p;15    }16  }17  pop() {18    const d = this.data;19    const top = d[0];20    const last = d.pop();21    if (d.length) {22      d[0] = last;23      let i = 0;24      while (true) {25        const l = 2 * i + 1, r = l + 1;26        let m = i;27        if (l < d.length && this.compare(d[l], d[m]) < 0) m = l;28        if (r < d.length && this.compare(d[r], d[m]) < 0) m = r;29        if (m === i) break;30        [d[i], d[m]] = [d[m], d[i]];31        i = m;32      }33    }34    return top;35  }36}37 38function findKthLargest(nums, k) {39  const heap = new MinHeap();40  for (const x of nums) {41    heap.push(x);42    if (heap.size > k) heap.pop();43  }44  return heap.peek();45}46 47// 347: bucket sort by frequency, O(n)48function topKFrequent(nums, k) {49  const freq = new Map();50  for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);51  const buckets = Array.from({ length: nums.length + 1 }, () => []);52  for (const [value, count] of freq) buckets[count].push(value);53  const result = [];54  for (let f = buckets.length - 1; f > 0 && result.length < k; f--) {55    result.push(...buckets[f]);56  }57  return result.slice(0, k);58}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Using a max-heap to find the k largest.

  Fix: That needs all n elements in the heap. A min-heap of size k is the efficient choice.

• Java PriorityQueue is a min-heap by default.

  Fix: Use Collections.reverseOrder() or a comparator for a max-heap.

• Comparator subtraction overflow.

  Fix: Use Integer.compare or Long for distances.

Interview questions

Practice problems