In a 2D DP table filled row by row, why does a transition that reads dp[i][j+1] fail silently?

middleshould knowfreq 50%

answer

which cells are final when this line runs?
the loop walks a dependency graph
the cell to the right is not written yet
it reads the seed value, not a result
zeros hide it, sentinels expose it

basics

~20 s

Row-major filling writes left to right, so dp[i][j+1] has not been computed yet — it still holds the table's seed value. The transition folds that seed into a max or a min as if it were a real result, producing a wrong answer with no crash and no warning.

solid answer

~50 s

An iteration order is valid only if, for every cell, every cell its transition reads is already final. Filling row by row and left to right makes reads of dp[i-1][j-1], dp[i-1][j] and dp[i][j-1] safe, because all three were written earlier in this pass or in an earlier row. A read of dp[i][j+1] breaks that rule: the cell to the right is still holding whatever the table was seeded with, so the comparison silently accepts a fabricated score. Nothing throws, because the index is in range and the seed value is a perfectly legal number — which is exactly why this survives a quick test. The fix is to correct the term to dp[i][j-1] if the recurrence meant the cell already computed, or to reverse the inner loop if the recurrence genuinely depends on larger column indices. Seeding with a sentinel rather than zero turns the failure loud.

An iteration order is valid only if, for every cell, every cell its transition reads is already final. Filling row by row and left to right makes reads of `dp[i-1][j-1]`, `dp[i-1][j]` and `dp[i][j-1]` safe, because all three were written earlier in this pass or in an earlier row. A read of `dp[i][j+1]` breaks that rule: the cell to the right is still holding whatever the table was seeded with, so the comparison silently accepts a fabricated score. Nothing throws, because the index is in range and the seed value is a perfectly legal number — which is exactly why this survives a quick test. The fix is to correct the term to `dp[i][j-1]` if the recurrence meant the cell already computed, or to reverse the inner loop if the recurrence genuinely depends on larger column indices. Seeding with a sentinel rather than zero turns the failure loud.

code

pseudocode · 8 lines

pseudocode

// dp[i][j] = best score aligning the first i readings of log A with the first j of log B
// boundaries dp[0][*] and dp[*][0] are seeded before the loops
for i in 1..n
    for j in 1..m
        dp[i][j] = max(dp[i-1][j-1] + score(i, j),   // pair reading i with reading j
                       dp[i-1][j]   + gap,           // drop reading i from log A
                       dp[i][j+1]   + gap)           // drop reading j from log B  <-- review
answer = dp[n][m]

go deeper

for a junior

Be ready to say which cells are already computed at a given point in a nested loop, and to notice that reading a not-yet-written cell returns whatever it was seeded with rather than raising an error.

for a middle

Explain the fill order as a topological order of the recurrence's dependency graph, and derive the loop direction from the transition's offsets instead of copying a familiar loop shape.

for a senior

Catch this in review with a question rather than a test run: at the moment this line executes, is that cell final? Argue for sentinel seeding so the failure is loud instead of plausible.

for a principal

Push the practice upstream: transitions documented with their read offsets, tables seeded with sentinels by default, and reviewers who treat a forward read as a correctness defect rather than a style nit.

Dependencies first, loops second

A recurrence defines a directed graph over cells: an arrow from A to B means computing B reads A. The recurrence is well-founded only if that graph is acyclic, and a fill order is valid only if it is a topological order of that graph — every cell computed after everything it reads. Nested loops are just a convenient way to walk such an order; they are not themselves a guarantee of one.

Consider a table over two logs of readings, where dp[i][j] is the best score for aligning the first i readings of one log with the first j of the other. The intended recurrence reads three neighbours: the diagonal (pair the two current readings), the cell above (drop a reading from the first log) and the cell to the left (drop a reading from the second). Those three arrows point up and left, so a row-major, left-to-right walk satisfies all of them.

Now suppose a review diff shows the third term reading the cell to the right instead of the left. The loop still runs. The index is in range for every j < m. But the cell to the right has not been assigned in this pass, so it still contains the table's initial value.

Why it is silent, and what that costs you

Three things conspire to hide the defect:

No memory error. The read is inside the allocated table, so nothing detects it.
The seed is a legal value. If the table was seeded with zeros — the reflex — then a computed zero and an unwritten zero are indistinguishable. The max cheerfully treats the unwritten cell as a real alignment worth zero, and if gap happens to be attractive relative to real scores, the fabricated branch wins and propagates.
Small inputs may not exercise it. On a one-row or one-column input the bad term is either out of the interesting range or dominated by the other terms, so a hand-checked tiny example agrees.

The result is a table that is partly the algorithm you designed and partly an artefact of allocation. Debugging that from the output alone is miserable, because the answer is not obviously absurd — it is just quietly too good.

One defensive habit turns this class of bug loud: seed with a sentinel, not zero. For a maximisation, seed unwritten cells with a very negative value; a fabricated branch then loses every comparison and either produces an obviously broken answer or is provably never selected. For reachability tables, seed "unreachable" rather than "reachable". The seed encodes a claim — "this state has not been established" — and zeros are a bad way to make that claim, because zero is usually also a legitimate result.

When does a right-to-left inner loop become correct?

The order is not sacred; the dependency graph is. If the state is defined over suffixes — dp[i] meaning "the best answer over items i..n" — its transition naturally reads larger indices, and the correct fill runs downward, from n toward 1. Same with a 2D table whose transition genuinely reads the cell to the right: fill each row right to left. What you may never do is write the loops first and hope.

The pathological case is worth naming: if a transition reads both the cell to the left and the cell to the right of the same row, no single-pass order exists, because the dependency graph has a cycle. That is not an iteration-order problem to be fixed by flipping a loop — it means the recurrence is not a valid recurrence, and the state must be redefined (often by adding a dimension that breaks the cycle, or by splitting the pass into two directional passes whose results are combined).

How to check an order without running anything

A thirty-second review procedure, and the one to describe out loud when asked:

List every cell the transition reads, as offsets from the cell being written.
Draw those offsets on a small grid.
For your loop order, confirm each offset points at a cell already written in this pass or seeded before it.
Any offset pointing forward in the traversal order is a bug; any pair of offsets pointing in opposite directions along the same axis means the recurrence itself is unsound.

That check is faster than the test run and catches the defect at the moment it is introduced, which is when it is cheapest. In review, the version of the question worth asking the author is simply: "at the moment this line executes, is that cell final?" — an author who cannot answer immediately has not thought about the order at all.

## Dependencies first, loops second A recurrence defines a directed graph over cells: an arrow from `A` to `B` means computing `B` reads `A`. The recurrence is well-founded only if that graph is acyclic, and a fill order is valid only if it is a **topological order of that graph** — every cell computed after everything it reads. Nested loops are just a convenient way to walk such an order; they are not themselves a guarantee of one. Consider a table over two logs of readings, where `dp[i][j]` is the best score for aligning the first `i` readings of one log with the first `j` of the other. The intended recurrence reads three neighbours: the diagonal (pair the two current readings), the cell above (drop a reading from the first log) and the cell to the left (drop a reading from the second). Those three arrows point up and left, so a row-major, left-to-right walk satisfies all of them. Now suppose a review diff shows the third term reading the cell to the **right** instead of the left. The loop still runs. The index is in range for every `j < m`. But the cell to the right has not been assigned in this pass, so it still contains the table's initial value. ## Why it is silent, and what that costs you Three things conspire to hide the defect: 1. **No memory error.** The read is inside the allocated table, so nothing detects it. 2. **The seed is a legal value.** If the table was seeded with zeros — the reflex — then a computed zero and an unwritten zero are indistinguishable. The `max` cheerfully treats the unwritten cell as a real alignment worth zero, and if `gap` happens to be attractive relative to real scores, the fabricated branch wins and propagates. 3. **Small inputs may not exercise it.** On a one-row or one-column input the bad term is either out of the interesting range or dominated by the other terms, so a hand-checked tiny example agrees. The result is a table that is *partly* the algorithm you designed and partly an artefact of allocation. Debugging that from the output alone is miserable, because the answer is not obviously absurd — it is just quietly too good. One defensive habit turns this class of bug loud: **seed with a sentinel, not zero.** For a maximisation, seed unwritten cells with a very negative value; a fabricated branch then loses every comparison and either produces an obviously broken answer or is provably never selected. For reachability tables, seed "unreachable" rather than "reachable". The seed encodes a claim — "this state has not been established" — and zeros are a bad way to make that claim, because zero is usually also a legitimate result. ## When does a right-to-left inner loop become correct? The order is not sacred; the dependency graph is. If the state is defined over **suffixes** — `dp[i]` meaning "the best answer over items `i..n`" — its transition naturally reads larger indices, and the correct fill runs downward, from `n` toward `1`. Same with a 2D table whose transition genuinely reads the cell to the right: fill each row right to left. What you may never do is write the loops first and hope. The pathological case is worth naming: if a transition reads **both** the cell to the left and the cell to the right of the same row, no single-pass order exists, because the dependency graph has a cycle. That is not an iteration-order problem to be fixed by flipping a loop — it means the recurrence is not a valid recurrence, and the state must be redefined (often by adding a dimension that breaks the cycle, or by splitting the pass into two directional passes whose results are combined). ## How to check an order without running anything A thirty-second review procedure, and the one to describe out loud when asked: 1. List every cell the transition reads, as offsets from the cell being written. 2. Draw those offsets on a small grid. 3. For your loop order, confirm each offset points at a cell already written in this pass or seeded before it. 4. Any offset pointing forward in the traversal order is a bug; any pair of offsets pointing in opposite directions along the same axis means the recurrence itself is unsound. That check is faster than the test run and catches the defect at the moment it is introduced, which is when it is cheapest. In review, the version of the question worth asking the author is simply: *"at the moment this line executes, is that cell final?"* — an author who cannot answer immediately has not thought about the order at all.

How do you verify a fill order without running the code?
Write the transition's reads as offsets from the cell being written, sketch them on a small grid, and confirm every offset points at a cell already final under your traversal. A valid loop order is exactly a topological order of the dependency graph, so any offset pointing forward in the walk is a bug you can see on paper.
When is a right-to-left inner loop the correct choice rather than a smell?
When the state is defined over suffixes or otherwise genuinely depends on larger indices — for example `dp[i]` meaning the best answer over items `i..n`. Its arrows point toward higher indices, so the fill must run downward. The order follows the dependency graph; neither direction is inherently right.
What if a transition needs both the cell to the left and the cell to the right?
Then the dependency graph has a cycle and no single-pass order exists, so flipping the loop cannot help. The recurrence is unsound as written: redefine the state, usually by adding a dimension that breaks the cycle, or split it into two directional passes whose results are combined afterwards.
Why does seeding with a sentinel make this class of bug easier to catch?
Because zero is usually a legitimate computed value, so an unwritten cell is indistinguishable from a real one. A strongly negative sentinel in a maximisation loses every comparison, so a fabricated branch either never wins or yields an obviously broken answer instead of a plausible, quietly optimistic one.

saying these in an interview costs you the question

Expects an out-of-range error rather than a wrong number
Adds a bounds check instead of fixing the order
Assumes any loop nesting works if the recurrence is right
Believes the table is fully populated before the loops start
Cannot say which cells are final at a given point in the pass

In a 2D DP table filled row by row, why does a transition that reads dp[i][j+1] fail silently?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

Dependencies first, loops second

Why it is silent, and what that costs you

When does a right-to-left inner loop become correct?

How to check an order without running anything

▾common follow-ups4 questions

▾red flags5 flags

§ context

▾related questions7 questions

▾related topics4 topics

Dependencies first, loops second

Why it is silent, and what that costs you

When does a right-to-left inner loop become correct?

How to check an order without running anything

answer

go deeper

context