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.
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.
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.
Merge k sorted linked lists into one sorted list.
Plan before you code
- Push (value, list index, node) for each head; the index breaks ties.
- Pop the smallest, append it, push its next node.
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
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}1fun kLargest(nums: IntArray, k: Int): List<Int> {2 val heap = PriorityQueue<Int>() // a min-heap3 for (x in nums) {4 heap.add(x)5 if (heap.size > k) heap.poll() // drop the smallest6 }7 val out = ArrayList<Int>()8 while (heap.isNotEmpty()) out.add(heap.poll())9 return out.reversed()10}1static int[] kLargest(int[] nums, int k) {2 PriorityQueue<Integer> heap = new PriorityQueue<>(); // a min-heap3 for (int x : nums) {4 heap.add(x);5 if (heap.size() > k) heap.poll(); // drop the smallest6 }7 int[] out = new int[heap.size()];8 for (int i = out.length - 1; i >= 0; i--) out[i] = heap.poll();9 return out;10}- TypeScript has no built-in heap: write a small array-backed one with a comparator.
- push: append, then sift up while smaller than the parent. O(log n).
- pop: move the last item to the root, then sift down. O(log n).
- 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
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}1fun mergeKLists(lists: List<ListNode?>): ListNode? {2 val heap = PriorityQueue<ListNode>(compareBy { it.value })3 for (head in lists) if (head != null) heap.add(head)4 val dummy = ListNode(0)5 var tail = dummy6 while (heap.isNotEmpty()) {7 val node = heap.poll()8 tail.next = node9 tail = node10 node.next?.let { heap.add(it) }11 }12 return dummy.next13}1static ListNode mergeKLists(ListNode[] lists) {2 PriorityQueue<ListNode> heap = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));3 for (ListNode head : lists) if (head != null) heap.add(head);4 ListNode dummy = new ListNode(0);5 ListNode tail = dummy;6 while (!heap.isEmpty()) {7 ListNode node = heap.poll();8 tail.next = node;9 tail = node;10 if (node.next != null) heap.add(node.next);11 }12 return dummy.next;13}Step by step
- A heap of each list's head, ordered by value (MinHeap from the template).
- Pop the smallest node and append it.
- Push the next node from the same list.
Complexity: O(N log k) time for N total nodes, O(k) space
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?
Heap or sort?
How do you get a max-heap?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Size-k min-heap, answer is heap[0].
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
Top K Frequent Elements
Return the k most frequent values, faster than O(n log n).
- Count frequencies.
- Bucket values by frequency: index = count, at most n buckets.
- Read buckets from the highest frequency down.
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}Complexity: O(n) time and space (bucket sort beats the heap here)
Find Median from Data Stream
Support add(x) and median() on a stream of numbers.
- A max-heap holds the smaller half, a min-heap the larger half.
- Route every number through the low heap so the halves stay ordered.
- Rebalance so the low half has the same size or one more.
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}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