/Projects
Coding patterns · 07 of 15

Heap / top-K

Keep the best K so far in a size-K heap.

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot heap / top-k from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

O(n log k) time, O(k) space Watch as reels
Part 1 of 5

Basics

The idea behind the pattern, why it is correct, and the clues in a question that point to it.

1.1Core idea

What the pattern does, in plain words.

A min-heap of size K holds the K largest seen so far; its top is the Kth largest. For merging, push the head of each list and repeatedly pop the smallest.

Why it works

A heap keeps the smallest (or largest) item at the top and restores its order in O(log n) after each push or pop. To keep the k largest of a stream, hold a min-heap of size k: its top is the weakest of the current top k, so it is the one to evict when something bigger arrives.

Typical cost: O(n log k) time, O(k) space

1.2Recognition signals

If a question has one of these clues, try this pattern first.

Kth largest or smallestTop K frequentMerge K sorted listsRunning medianAlways process the cheapest next item
Part 2 of 5

Question

A classic interview problem from this family. Read it carefully and plan the approach before writing any code.

2.1Merge K Sorted Lists

The problem statement, then the plan you would say out loud.

Problem

Merge k sorted linked lists into one sorted list.

Plan before you code

  1. Push (value, list index, node) for each head; the index breaks ties.
  2. Pop the smallest, append it, push its next node.
Part 3 of 5

Detailed answer

First the reusable template, then the worked solution built from it and a walk through it one step at a time.

3.1Template

Memorise this shape. Most problems in this family are this code plus one twist.

K largest with a size-k min-heap

k-largest-sizek.tsTypeScript
1class MinHeap<T> {2  private a: T[] = [];3  private less: (x: T, y: T) => boolean;4  constructor(less: (x: T, y: T) => boolean) {5    this.less = less;6  }7  get size(): number { return this.a.length; }8  peek(): T | undefined { return this.a[0]; }9  push(x: T): void {10    const a = this.a;11    let i = a.push(x) - 1;12    while (i > 0) {13      const p = (i - 1) >> 1;14      if (!this.less(a[i], a[p])) break;15      [a[i], a[p]] = [a[p], a[i]];16      i = p;17    }18  }19  pop(): T | undefined {20    const a = this.a, top = a[0], last = a.pop()!;21    if (a.length === 0) return top;22    a[0] = last;23    for (let i = 0; ; ) {24      const l = 2 * i + 1, r = l + 1;25      let m = i;26      if (l < a.length && this.less(a[l], a[m])) m = l;27      if (r < a.length && this.less(a[r], a[m])) m = r;28      if (m === i) return top;29      [a[i], a[m]] = [a[m], a[i]];30      i = m;31    }32  }33}34 35function kLargest(nums: number[], k: number): number[] {36  const heap = new MinHeap<number>((x, y) => x < y);37  for (const x of nums) {38    heap.push(x);39    if (heap.size > k) heap.pop();   // drop the smallest40  }41  const out: number[] = [];42  while (heap.size) out.push(heap.pop()!);43  return out.reverse();44}
44 linesUTF-8TypeScript
  1. TypeScript has no built-in heap: write a small array-backed one with a comparator.
  2. push: append, then sift up while smaller than the parent. O(log n).
  3. pop: move the last item to the root, then sift down. O(log n).
  4. Size-k min-heap: push, then evict the smallest once we exceed k.

3.2Solution

Strict TypeScript, type-checked and tested.

Merge K Sorted Lists

merge-k-sorted.tsTypeScript
1function mergeKLists(lists: (ListNode | null)[]): ListNode | null {2  const heap = new MinHeap<ListNode>((x, y) => x.val < y.val);3  for (const head of lists) if (head) heap.push(head);4  const dummy: ListNode = { val: 0, next: null };5  let tail = dummy;6  while (heap.size) {7    const node = heap.pop()!;8    tail.next = node;9    tail = node;10    if (node.next) heap.push(node.next);11  }12  return dummy.next;13}
13 linesUTF-8TypeScript

Step by step

  1. A heap of each list's head, ordered by value (MinHeap from the template).
  2. Pop the smallest node and append it.
  3. Push the next node from the same list.

Complexity: O(N log k) time for N total nodes, O(k) space

Part 4 of 5

Q&A

What interviewers ask once your code works, and problems to try on your own.

4.1Interview questions

Answer out loud, then open.

Why a min-heap for the k largest?
You need instant access to the smallest of the k you are keeping, because that is the one to throw out. The total cost is O(n log k).
Heap or sort?
Sorting is O(n log n) and needs all the data up front. A size-k heap is O(n log k) and works on a stream.
How do you get a max-heap?
Flip the comparator. Where only a min-heap is built in, push negated values.

4.2Solo practice

Try these without looking; open the hint only when stuck.

MediumKth Largest Element in an Array
Hint

Size-k min-heap, answer is heap[0].

Part 5 of 5

Extra depth

More fully worked problems in the same family, and the mistakes that cost offers.

5.12 more worked problems

Each one: the problem, the plan, the code and its cost.

Show detailsHide details
Medium

Top K Frequent Elements

Return the k most frequent values, faster than O(n log n).

  1. Count frequencies.
  2. Bucket values by frequency: index = count, at most n buckets.
  3. Read buckets from the highest frequency down.
top-k-frequent.tsTypeScript
1function topKFrequent(nums: number[], k: number): number[] {2  const counts = new Map<number, number>();3  for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);4  const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);5  for (const [x, c] of counts) buckets[c].push(x);6  const out: number[] = [];7  for (let c = buckets.length - 1; c > 0 && out.length < k; c--) {8    for (const x of buckets[c]) {9      out.push(x);10      if (out.length === k) break;11    }12  }13  return out;14}
14 linesUTF-8TypeScript

Complexity: O(n) time and space (bucket sort beats the heap here)

Hard

Find Median from Data Stream

Support add(x) and median() on a stream of numbers.

  1. A max-heap holds the smaller half, a min-heap the larger half.
  2. Route every number through the low heap so the halves stay ordered.
  3. Rebalance so the low half has the same size or one more.
find-median-from.tsTypeScript
1class MedianFinder {2  private low = new MinHeap<number>((x, y) => x > y);    // max-heap3  private high = new MinHeap<number>((x, y) => x < y);   // min-heap4  add(x: number): void {5    this.low.push(x);6    this.high.push(this.low.pop()!);7    if (this.high.size > this.low.size) this.low.push(this.high.pop()!);8  }9  median(): number {10    if (this.low.size > this.high.size) return this.low.peek()!;11    return (this.low.peek()! + this.high.peek()!) / 2;12  }13}
13 linesUTF-8TypeScript

Complexity: O(log n) add, O(1) median

5.2Traps

Bugs and misreadings that come up again and again with this pattern.

Show detailsHide details
  • Needing a max-heap: push negated values
  • Comparing nodes on ties: add an index
AI Engineer · Heap / top-K