Heaps And Selection Algorithms

What's being tested

Heap-based selection and sorted-structure traversal: finding top-k, kth, or median-like elements without fully sorting or materializing all candidates. Interviewers probe whether you can exploit sorted inputs, bound memory to O(k), and reason clearly about duplicates, negative values, and boundary cases.

Patterns & templates

• Max-heap for k smallest — scan n values, keep heap size k; use negated values in Python; O(n log k) time, O(k) space.

• Min-heap k-way merge — push one head per sorted list/row, repeatedly heappop; complexity O(k log m) for m sources.

• Best-first search over pair sums — start at (0,0), push neighbors (i+1,j) and (i,j+1); use visited to avoid duplicates; O(k log k).

• Sorted matrix selection — either min-heap over rows, O(k log n), or value-space binary search with count <= mid, O(n log range).

• Quickselect — average O(n) for kth element when input is unsorted; handle equal pivots with 3-way partitioning.

• Median of two sorted arrays — binary search partition, not heap; target left size (m+n+1)//2, check maxLeft <= minRight.

• Tie and duplicate handling — duplicate values may be valid outputs, but duplicate heap states like (i,j) should usually be suppressed.

Common pitfalls

Pitfall: Generating all pair sums or flattening a matrix is usually O(nm log nm) or O(n^2 log n) and misses the intended selection pattern.

Pitfall: Confusing “k smallest elements” with “kth smallest element”; one returns a collection, the other returns a single rank statistic.

Pitfall: Forgetting k == 0, k > n, empty arrays, duplicate values, and negative numbers leads to brittle code even if the core heap idea is correct.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.