Kth and Selection

What is this?

Merging sorted piles is something people do without thinking. Given three sorted stacks of cards, you look at the three top cards, take the smallest, and immediately look at the new top of that pile. You never examine the whole of any stack. The heap is that glance at the tops — and it stays exactly as large as the number of piles, no matter how many cards there are.

The second idea in this chapter is stranger and sometimes better: do not store anything at all. Guess a value, count how many elements fall below it, and binary-search the guess.

💡 Fun fact: Kth Smallest Element in a Sorted Matrix has two good answers with genuinely different trade-offs. The heap treats each row as a sorted list and merges: O(k log n) time, O(n) space. Binary search on the value counts how many entries are ≤ mid by walking a staircase from the bottom-left corner: O(n log(max−min)) time and O(1) space. Neither dominates — and being able to say which you would pick, and why, is worth more than either implementation.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

---

The one-line idea: you rarely need the full ordering. A heap holding one entry per source merges any number of sorted streams in O(n log k), and when even that is too much memory, binary-searching the value replaces storage with counting.

---

1. The k-way merge

import heapq

heap = [(rows[i][0], i, 0) for i in range(len(rows))]   # (value, which source, index in it)
heapq.heapify(heap)
for _ in range(k - 1):
    val, src, idx = heapq.heappop(heap)
    if idx + 1 < len(rows[src]):
        heapq.heappush(heap, (rows[src][idx + 1], src, idx + 1))
return heap[0][0]

Each entry carries where it came from, because on popping you must refill from that same source. The heap therefore never holds more than k items, and that bound is the entire performance argument: merging a million elements from four sorted files costs log 4 per element, not log 1000000.

2. Tracking a window across k lists

Smallest Range Covering Elements from K Lists runs the same machinery with a different question. Keep one element from every list in a min-heap and track the maximum among them separately. The current window is [heap top, tracked max] — it necessarily contains at least one element from each list. Pop the minimum, advance that list, update the max, and record the window if it is the smallest so far. The moment any list is exhausted, no further window can cover everything, so you stop.

3. Binary search on the value

When the answer is a number rather than a specific stored element, you can search the value range directly. The requirement is a monotonic counting function: count(x) = how many elements are ≤ x must be non-decreasing in x. Then the smallest x with count(x) ≥ k is the k-th smallest value.

For a row-and-column-sorted matrix, counting is a staircase walk from the bottom-left: move up when the current value is too big, move right when it is small enough, adding a whole column's worth each time. That is O(n) per count, O(n log(range)) overall, and O(1) space.

---

4. A 30-second worked example

Matrix rows [1,5,9], [10,11,13], [12,13,15], and k = 5.

Three rows, nine elements, and the heap held at most three entries throughout.

---

5. Where you'll actually meet this

• External sorting. Merging sorted runs that do not fit in memory is exactly the k-way merge — the heap is bounded by the number of runs, not the data size.
• Log aggregation. Interleaving timestamped logs from many servers into one ordered stream.
• Search engines. Merging posting lists from multiple shards, taking the top-k results without materialising everything.
• Database query execution. Merge-join and ORDER BY … LIMIT k over partitioned inputs.
• Percentile monitoring. Finding the p99 latency over a huge sample, where binary-search-on-value avoids storing the sample at all.

---

6. Problems in this chapter

▶ Kth Smallest Element in a Sorted Matrix

The k-th smallest in a row- and column-sorted matrix. Heap merge in O(k log n), or binary search on the value in O(1) space — know both and the trade-off between them.
Pattern: k-way merge, or binary search on the answer. Target: O(k log n) time / O(n) space, or O(n log(range)) / O(1).

▶ Smallest Range Covering Elements from K Lists

The narrowest range containing at least one number from each of k sorted lists. One element per list in a min-heap plus a tracked maximum; stop when any list runs out.
Pattern: k-way merge with a window. Target: O(n log k) time, O(k) space.

▶ Minimize Deviation in Array

Minimise the gap between the largest and smallest after doubling odds and halving evens. Normalise every number to its maximum reachable value, then repeatedly shrink the current maximum with a max-heap while tracking the minimum.
Pattern: normalise, then greedily reduce the extreme. Target: O(n log n log(max)) time, O(n) space.

---

7. Common pitfalls 🚫

• Not storing the source index. Without it you cannot refill after a pop, and the merge stalls.
• Pushing everything into the heap. That is O(n log n) and throws away the whole k-bound advantage.
• Forgetting Python's heapq is min-only. Max-heaps need negated values, and negation flips your tie-breaking too.
• Comparing unorderable payloads. When two tuples tie on the first field, Python compares the next — put an index before any object that cannot be compared.
• Continuing after a list is exhausted in the smallest-range problem. Once one list is done, no valid window remains.
• Assuming binary search on the answer always wins. It needs a monotonic count and a bounded value range; without both, the heap is the right tool.
• Off-by-one on k. Pop k-1 times and read the top, or pop k times and take the last — mixing the two is the classic slip.

---

8. Key takeaways

1. The heap is bounded by the number of sources, not the data. That is the whole performance story of a k-way merge.
2. Carry provenance in the heap entry so you know which source to refill.
3. A window across k lists is the min in the heap and a separately tracked max.
4. Binary search the value when memory matters — replace storage with a monotonic count.
5. Neither approach dominates. State the trade-off; the interviewer is usually asking for exactly that.
6. Normalise before you optimise. Minimize Deviation only becomes tractable once every number is mapped to its maximum reachable form.
7. Why interviewers like it: "sort it all" is always available and always suboptimal here, so the conversation goes straight to what you actually need to store.

Order: Kth Smallest Element in Sorted Matrix → Smallest Range Covering Elements from K Lists → Minimize Deviation in Array.