Frontier heaps for k-th smallest pairs

To find the k pairs with the smallest sums from two sorted lists, picture the sums as a grid: row i, column j holds a[i] + b[j], and the grid rises along every row and down every column. The smallest pair sits in the corner, and every later one lies next to a pair already taken, so a heap that holds only that edge, the frontier, hands out the pairs in order with O(k log k) work instead of pricing all n × m pairs. The same frontier finds the k-th smallest value of any matrix whose rows and columns are sorted. The problem, its brute force and the signal follow.

The problem: the k cheapest combos on a canteen menu

• Mains [100, 130, 200], sides [20, 50, 90] and k = 5 give (0, 0) 120, (0, 1) 150, (1, 0) 150, (1, 1) 180 and (0, 2) 190. The two combos at 150 come in order of the main.
• Mains [5], sides [1, 1] and k = 3 give (0, 0) and (0, 1): only two combos exist.

The brute force, and why it fails at these sizes

Price every combo, sort them all and keep the first k. It is correct, but at the limits the grid has n × m = 10¹⁰ cells: 80 GB just to hold their prices as 8-byte numbers, then a sort of 10¹⁰ items to keep 10,000 of them. A heap of size k over all the combos saves the memory, yet it still prices every one of the 10¹⁰.

# The brute force: price every (main, side) combo, sort them all and keep the first k. Correct, and it shows what
# the answer must look like, but the work is the full grid of combos.


def k_cheapest_brute(mains, sides, k):
    combos = [(m + s, i, j) for i, m in enumerate(mains) for j, s in enumerate(sides)]
    combos.sort()  # by price, then by the main's position, then by the side's
    return combos[:k], len(combos)


for mains, sides, k in (([100, 130, 200], [20, 50, 90], 5), ([5], [1, 1], 3)):
    best, priced = k_cheapest_brute(mains, sides, k)
    print(f"k = {k}:", ", ".join(f"({i}, {j}) {price}" for price, i, j in best), f"[{priced} combos priced]")

n = m = 100_000
print(f"at the limits: {n:,} mains x {m:,} sides = {n * m:,} combos to price and sort, to keep k = 10,000")
print(f"the prices alone, as 8-byte numbers: {n * m * 8 / 10**9:,.0f} GB")

k = 5: (0, 0) 120, (0, 1) 150, (1, 0) 150, (1, 1) 180, (0, 2) 190 [9 combos priced]
k = 3: (0, 0) 6, (0, 1) 6 [2 combos priced]
at the limits: 100,000 mains x 100,000 sides = 10,000,000,000 combos to price and sort, to keep k = 10,000
the prices alone, as 8-byte numbers: 80 GB

What to notice

• The grid is sorted twice. Prices rise along every row, because the sides are sorted, and down every column, because the mains are.
• So a combo can be the next cheapest only once the combo to its left and the one above it are taken. The candidates form a thin edge around the taken corner, never the whole grid.

Keeping that edge in a min-heap and taking its cheapest combo again and again is the pattern of this lesson. After three combos, the edge in the example holds three candidates, and the cheapest of them, 180, comes next.

The frontier, step by step: rows started on demand Pro: opens with a Pro, Premium or Ultimate pass