When a 2D DP is collapsed to one array, why does the loop direction become a correctness issue?
answer
- one array is two rows superimposed
- a cell means old value until written
- which reads happen after a write
- check whether reads point below the write
- sweep so reads land in unvisited cells
basics
~20 sDirection decides whether a read still sees the previous pass's value. In one array a write can clobber a cell the same pass later reads, so the wrong order silently computes a different recurrence — a wrong answer, not a slow one.
solid answer
~50 sCollapsing two rows into one array superimposes two generations in the same cells. A cell holds the previous pass's value until this pass writes it, and the current pass's value afterwards — so the meaning of `cur[c]` depends on whether the sweep has reached `c` yet. If each write at index `c` reads lower indices, sweeping upward means those lower cells were already overwritten, and the transition quietly reads this pass's results instead of the previous pass's. Sweeping downward keeps every read inside the not-yet-visited region, which still holds the old generation. That is the whole equivalence proof: the 1D version equals the 2D version only under a read/write ordering argument, so the direction is a correctness property with an invariant behind it, not a style choice. Both loops compile, both look reasonable in review, and small inputs often agree.
code
pseudocode · 10 lines// cur[c] = best value for weight limit c using the crates seen so far
for c in 0..C
cur[c] = 0
for i in 1..n
for c in C down to weight[i] // descending is load-bearing
cand = cur[c - weight[i]] + value[i]
if cand > cur[c]
cur[c] = cand
...
answer = cur[C]go deeper
Recall that a single array stores two generations of values and that a cell means the old value only until this pass writes it. Knowing that the sweep direction can change the result is enough at this level.
Point at each read index in the loop body and say whether the current pass has written it yet, then derive the required direction from that instead of memorizing 'go backwards'. Be able to state the invariant in one sentence.
Show that you would catch this in review and prove it, not argue it: randomized differential testing against the uncompressed version, and a comment recording the invariant rather than the mechanic.
Set the norm for the codebase. Decide whether compressed DP may ship without its uncompressed reference implementation and a cross-check, and weigh the halved memory against code that a future maintainer can break with a plausible cleanup.
## One array is two rows superimposed When a DP whose transition reads only the row behind it is compressed to a single array, that array plays two roles at once. Before the current pass writes index `c`, `cur[c]` still holds the previous pass's value for that state. After the write, it holds the current pass's value. Same storage, two different meanings, separated in time by the sweep. Every correctness argument about the compressed form is an argument about which side of that line each read lands on. ``` // cur[c] = best value for weight limit c using the crates seen so far for i in 1..n for c in C down to weight[i] // descending is load-bearing cand = cur[c - weight[i]] + value[i] if cand > cur[c] cur[c] = cand ... answer = cur[C] ``` The write is at `c`; the read is at `c - weight[i]`, strictly below `c`. Sweeping `c` downward means the region below `c` has not been visited yet this pass, so `cur[c - weight[i]]` is still the previous generation — exactly what the 2D form's `best[i-1][c - weight[i]]` meant. ## The invariant, stated properly *At the moment the pass writes index `c`, every index in the not-yet-visited region still holds the previous pass's value.* A one-array compression is valid precisely when every read index falls in that region. That gives a mechanical rule with no memorization: find where the reads point relative to the write, then sweep so the reads land in unvisited territory. Reads below the write index mean a descending sweep; reads above it mean an ascending sweep. Reads on **both** sides mean no sweep order works — one array is impossible and you keep two rows (or copy the read range into a scratch buffer first, which is just two rows wearing a disguise). ## Why the flipped loop is so dangerous An ascending sweep in the fragment above is not a crash, an exception, or an out-of-range access. It is a perfectly well-defined computation of a *different* recurrence — one where a state may consume a result the same pass just produced. There are problems where that self-referential read is exactly the intent, which is the deepest point here: the sweep direction is not decoration on top of the algorithm, it **is** part of which recurrence you wrote. So a reviewer who flips a loop "for consistency with the other one" has changed the algorithm, not the formatting. Worse, the two versions often agree on small inputs. With a single item, or with inputs where the extra reachable states never beat the honest ones, both directions return the same number. A test suite full of tiny hand-built cases passes, and the divergence shows up on production-sized input where nobody can trace it by hand. ## How to keep it out of the codebase Three things work, in increasing order of reliability. First, a comment on the loop that states the invariant rather than the mechanic: not "loop backwards", which invites a well-meaning cleanup, but "descending so the reads below `c` still hold the previous pass". Second, a review habit: for every read index in the body, ask out loud whether this pass has already written it. That check takes seconds and catches the entire bug class. Third, and strongest, differential testing — keep the plain 2D implementation as a reference and assert on randomized inputs that the compressed version matches it. The 2D version is easy to get right, cheap to run on small random cases, and turns an invisible semantic difference into a failing test. ## What is genuinely equivalent The two-row form has none of this hazard: `prev` and `cur` are distinct storage, so no write can disturb a read, and the direction of the inner sweep is genuinely free. That is why the two-row version is the sane default and the one-array version is a deliberate step taken when halving the memory actually matters. Halving is all it ever buys — two rows and one row are both linear in the row width, so the one-array form is a constant-factor optimization purchased with a proof obligation. ## The wrong answers "Both directions give the same result, one is just faster" — no; they compute different things. "The 1D version is the 2D version with less memory" — only under the ordering argument, which is the entire content of the transformation. "Tests are green, so it is fine" — small inputs routinely fail to separate the two recurrences.
- The tests are green after someone flips that inner loop. How do you catch it in review?For every read index in the loop body, ask whether the current pass has already written it; that single check catches the whole bug class in seconds. Then make it systematic: keep the uncompressed two-row or 2D implementation as a reference and assert on randomized inputs that both agree. Small hand-built cases frequently fail to separate the two recurrences, so randomized differential testing is the only check that reliably does.
- Is an ascending sweep always a bug?No. Ascending computes a different but perfectly well-defined recurrence, one where a state may consume a result the same pass just produced, and for some problems that is exactly the intent. The point is that direction encodes which recurrence you wrote. It has to be chosen deliberately and commented with the invariant it maintains, not left to whichever way the loop was typed.
- What if the transition reads an index above the one being written?Then the mirror image holds: sweep ascending, so the higher indices are still untouched and carry the previous pass's values. The general rule is to sweep so every read index falls in the region the pass has not visited yet. If reads land on both sides of the write, no order works — keep two rows instead.
saying these in an interview costs you the question
- Calls the sweep direction a style preference
- Says both directions agree, one is just faster
- Claims the 1D form is the 2D form with less memory, nothing else
- Reverses the outer loop instead of the inner sweep
- Trusts green small-input tests to prove equivalence