What do you give up by compressing a min-cost grid route DP to a single rolling row?

## What the compression does The cheapest right-and-down route over a terrain-cost grid obeys `best[i][j] = cost[i][j] + min(best[i-1][j], best[i][j-1])`. Every cell depends on the row above and on its own row's left neighbour, and on nothing older. That is the licence to keep one row instead of the whole table: as the sweep moves left to right, the entry at index `j` still holds the row above's value at the moment it is read, and index `j-1` was already overwritten with this row's value. One read of each, then the overwrite. The sweep direction is load-bearing. Going from high index down to low, `j-1` would still hold the row above, so the recurrence would combine the cell above with the cell above-left — a different, wrong problem. Nothing crashes; the numbers simply come out wrong on grids where those two cells differ, which is most of them. ## What it costs and what it saves | Property | Full table | Rolling row | |---|---|---| | Time | `O(m*n)` | `O(m*n)` — identical | | Working memory | one number per cell | one row of numbers | | Cheapest cost available | yes | yes | | Cheapest route recoverable | yes, by walking back | no | Compression buys memory and nothing else. Claiming it also speeds things up is a common overreach — the same number of cells is visited either way, though the smaller footprint can help a large grid stay in fast memory, which is a constant-factor effect, not an asymptotic one. Orient the sweep along the shorter dimension so the retained row is `min(m, n)` wide. ## Recovering the route when the caller needs it A robot-routing service usually needs the aisle-by-aisle route, not just its price. Three options, in increasing cleverness: **Keep the full table.** Simplest and often correct. One number per cell, then walk back from the destination comparing the two predecessors. Fine until the grid is large enough that the table dominates the process's memory. **Store one decision bit per cell.** During the compressed sweep, record for each cell which predecessor won — above or left. That is a single bit, against a full-width number in the naive table, so the footprint drops by roughly the width of a number in bits while remaining fully sufficient to walk the route back from the destination. It is still `O(m*n)` memory, just with a far smaller constant, and it is the option most production code lands on. **Split at the middle row.** Because every legal route moves down monotonically, it passes through exactly one cell of every row — including the middle one. So sweep forward from the start to the middle row, sweep backward from the destination to the middle row, add the two arrays elementwise, and the smallest entry names the column where the optimal route crosses. That fixes one cell of the answer; recurse on the two halves it splits the grid into. Each level of recursion halves the work, so the total is about twice a single sweep, and the memory never exceeds a row plus the recursion's own bookkeeping. This is the divide-and-conquer idea behind linear-space sequence alignment, applied to a grid, and it is the only option that keeps memory row-sized when the grid is genuinely huge. ## Choosing between them The decision is driven by what the caller consumes and what the memory ceiling is, not by which is most elegant. If the answer is a number on a dashboard, compress and stop. If a route is displayed once per request on grids of a few thousand cells, keep the full table — the code is shorter and the memory is nothing. If routes are computed continuously on very large grids under a fixed per-process ceiling, decision bits first, and the middle-row split only when even a bit per cell is too much. Each step up costs code that a future engineer must understand, and the middle-row version in particular is easy to get subtly wrong in the backward sweep's index convention, so it earns its place only when the memory pressure is real and measured. ## What an interviewer is listening for That you name the invariant justifying the single row, that you know the sweep direction is not free choice, that you separate *time unchanged* from *memory reduced* rather than blurring them, and above all that you ask what the caller actually needs before optimizing. A candidate who compresses to one row and then confidently offers to "just backtrack from the end" has not understood what was thrown away.