Staircase — workshop

The LC 373 k-smallest-pair-sums walk drawn on the sum matrix it never builds — a min-heap of boundary cells, the taken region as a staircase that dents inward on every pop and heals as the neighbours are pushed, with the seeding switchable between one-parent-per-cell, a visited set, and the naive version that pops a cell twice.

Two sorted arrays on the axes, and the grid between them holds every pair sum. Rows are non-decreasing, columns are non-decreasing, and the grid as a whole is not sorted — which is the whole problem. Find K Pairs with Smallest Sums (LC 373) asks for the k smallest cells, and the only cells that can be the next one sit on the boundary of what has already been taken. So the piece draws that: a min-heap of boundary cells in amber, the taken region in teal with its edge drawn as a white staircase, and on every tick the root pops (the staircase dents inward by one cell) and the cells just past it are pushed (the dent heals, the boundary is whole again). The answer grows as a row of chips underneath.

Three ways to seed and expand the heap, switchable on the same instance:

seed a column — push (i, 0) for the first min(m, k) rows; popping (i, j) pushes only (i, j + 1). Every cell has exactly one parent, so no cell can enter the heap twice and there is no visited set to keep. The heap never holds more than min(m, k) cells.
corner + visited set — push (0, 0); popping pushes both (i + 1, j) and (i, j + 1), and a set refuses any cell that has already been offered. Correct, at the cost of the set — watch the purple refused marks.
corner, no set — the same, without the guard. A cell reachable from two parents enters twice (the red ×2 in its corner) and is popped twice, so the answer repeats a pair and a real pair never arrives. The final readout counts exactly how many.

Dim the grid (the d key) hides every cell the algorithm never touched. That is the part the brief was pointing at: the sums were only ever coordinates, the counter under the side pane says how many of the m × n cells were actually computed, and the matrix was a fiction the algorithm agreed to believe in for the length of the walk.

Presets: the LC example ([1,7,11] × [2,4,6], k = 3), a ties case ([1,1,2] × [1,2,3], where equal values are fine because dedup is on coordinates), and random sorted arrays up to 8 × 8. Step with the arrow keys, or let it run.

Reuse

src/staircase.js is a framework-free ES module:

makeSorted(n, max = 40) — n random integers in [1, max], sorted.
CellHeap — a min-heap of { i, j, sum } keyed on sum, then (i, j); the tie-break is what makes a run draw the same way twice. Counts key comparisons.
simulate(nums1, nums2, k, mode) — mode is 'rows' | 'corner' | 'naive'; returns { frames, result, duplicates, touched, heapMax }, one frame per heap event (frame 0 is the seed) with copies of the heap, the cumulative output, and what each push did ('push', 'seen', 'edge'). Same trace-per-tick shape as sift and rho, so a renderer can scrub in any order.
staircase(taken, m) — the taken prefix of each row, which is the whole boundary: the popped set is always a down-set of the grid, so one number per row describes it exactly.

No rendering or timers in the module; the canvas demo is reference code.

Gotchas

The down-set claim (and so the staircase drawing) relies on the heap’s tie-break: with equal sums the lower (i, j) pops first. A real implementation with an arbitrary tie order still returns a correct answer, but its taken region can briefly fail to be a staircase.
In naive mode the run always makes exactly k pops, so the duplicates are in the answer, not extra work on top of it — the count in the readout is the number of correct pairs that were displaced.
k is clamped to m × n; rows mode seeds only min(m, k) rows, which is the O(min(m, k)) space bound the write-up quotes.
The demo bundles its own copy of staircase.js (self-contained by contract); re-copy after editing src/.