Why must a palindrome interval DP table be filled by increasing substring length?
answer
- which cell does the recurrence read?
- peeling both ends shrinks the span
- one row down, one column left
- row-major writes rows top to bottom
- so order the passes by span size
basics
~20 sThe recurrence reads dp[i+1][j-1] — a shorter interval sitting one row below and one column left. A plain row-by-row, left-to-right fill reaches that cell before writing it, so ordering by span length guarantees every dependency is already computed.
solid answer
~50 sFor the contiguous palindrome table, `dp[i][j]` is true when `s[i] == s[j]` and the interval inside it, `dp[i+1][j-1]`, is already known to be a palindrome. That dependency points to a **shorter** interval, and in row/column terms it lives one row down and one column left. The obvious double loop — `i` ascending outer, `j` ascending inner — reads row `i+1` before it has been written, so it consumes uninitialised cells. Iterating by span length instead (`len` from 1 upward, with `i` from 0 and `j = i + len - 1`) puts every dependency in a strictly earlier pass. Two other orders work for the same reason: `i` descending with `j` ascending, or column-major with `j` ascending. The bug is silent — with cells defaulting to false the table simply never reports a long palindrome — so it survives tests built on short inputs.
code
pseudocode · 9 linesfor i in 0..n-1:
for j in i..n-1:
if s[i] != s[j]:
dp[i][j] = false
else if j - i < 3:
dp[i][j] = true
else:
dp[i][j] = dp[i+1][j-1]
...go deeper
Be ready to say that the palindrome recurrence checks the two outer characters and then the stretch inside, so shorter spans must be computed before longer ones.
Explain the dependency in row and column terms, give the span-length loop precisely with its index arithmetic, and name at least one alternative order that also works.
Show the reviewer instinct: state which cells a recurrence reads and whether the loop has written them, and describe the silent truncation the wrong order produces in results rather than in errors.
Own how this class of bug is prevented at scale — where the ordering reflex is taught, whether tables are validated against a brute-force oracle on small inputs, and when to avoid the table entirely.
## The recurrence and the shape of its dependency Define `dp[i][j]` = "the stretch from index i to index j inclusive reads the same forwards and backwards". Then: ``` dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1] for j - i >= 3 dp[i][j] = (s[i] == s[j]) for j - i <= 2 ``` The base cases cover spans of length 1, 2 and 3, where peeling the two ends leaves nothing or a single character — always symmetric. Everything longer defers to the interval **strictly inside** it. That is the whole story: `dp[i][j]` depends on a cell with a **larger row index and a smaller column index**. Draw the table with rows as start index and columns as end index; only the upper triangle is meaningful (`j >= i`), and each cell points diagonally down-left to its dependency. ## Why the natural double loop is wrong The fragment attached to this question fills row by row: `i` from 0 upward, `j` from `i` upward. When it computes `dp[i][j]` for a long span it reads `dp[i+1][j-1]`, which sits in row `i+1` — a row this loop has not reached yet. The value read is whatever the table was initialised to. If the table is initialised to false (the usual default), the symptom is precise and quiet: spans of length up to 3 are answered correctly by the base-case branch, and **every longer span is reported as not a palindrome**. The routine therefore caps its answer at 3, no matter the input. Nothing crashes, no index goes out of range, and a test suite whose fixtures happen to have short answers passes green. Reviewers catch this by asking one question of any interval DP: *which cells does this recurrence read, and has the loop written them yet?* ## The orders that are correct Three fills satisfy the dependency, and it is worth being able to name more than one: 1. **By span length** (the canonical one). `len` from 1 to n; for each, `i` from 0 to n-len, and `j = i + len - 1`. Every dependency has span `len - 2`, completed two passes earlier. 2. **Row index descending.** `i` from n-1 down to 0, `j` from `i` upward. Row `i+1` is entirely finished before row `i` starts. 3. **Column index ascending, outer.** `j` from 0 upward, `i` from `j` down to 0. Column `j-1` is entirely finished before column `j` starts. All three cost O(n^2) time and, in their plain form, O(n^2) space in table cells. Memoised recursion sidesteps the question entirely: it computes a dependency on demand the first time it is needed, so no explicit order is required. The price is recursion depth proportional to the span, and recursion depth is space — a fact people forget when they call the memoised version "the same but with less bookkeeping". ## What the extra space buys, and when you can drop it Because the dependency only ever reaches row `i+1`, the length-descending order can keep just two rows and answer "what is the longest symmetric run?" in O(n) space. But then you have thrown away the table, and the table was the point: its value is answering "is the stretch i..j symmetric?" in constant time for **any** pair, over and over. That is what an enclosing computation wants — for instance one that partitions a read into the fewest symmetric segments, which consults palindromicity for a great many pairs. If all you want is one longest run, expanding around centres gives the same O(n^2) time with O(1) space and no fill-order trap at all. ## The same trap in its other disguise The subsequence variant of the table has the same dependency shape: ``` if s[i] == s[j]: dp[i][j] = dp[i+1][j-1] + 2 else: dp[i][j] = max(dp[i+1][j], dp[i][j-1]) ``` Here the reads are one row below and one column left — so a row-ascending fill is wrong for exactly the same reason, and the failure is again silent: lengths come out too small rather than absurd. Any recurrence whose interval shrinks from both ends inherits this ordering obligation, which is why "iterate by span length" is the reflex worth building rather than a fact to memorise per problem. ## How to answer in an interview Name the dependency cell, say where it lives relative to the cell being written, then give the order that guarantees it is ready and one alternative. Adding the symptom — "with a false-initialised table you silently cap the answer at length 3" — signals that you have actually debugged one of these rather than recited the loop.
- With cells defaulting to false, what does the broken fill actually output?It caps the answer at length 3. Spans of length 1 to 3 are settled by the base-case branch, and every longer span reads an unwritten cell that still holds false. Nothing crashes and no index goes out of range, so the failure looks like a modelling mistake rather than a loop-order bug.
- Is filling by span length the only correct order?No. Iterating the start index downward with the end index upward also works, since row i+1 finishes before row i begins; so does an outer loop over the end index ascending, which finishes column j-1 first. All three respect the same diagonal dependency and cost O(n^2).
- Does memoised recursion avoid the problem, and what does it cost?It avoids the ordering question because each dependency is computed on first use. The cost is stack depth proportional to the span being solved, and that depth counts as space — so the memoised version is not free relative to the iterative table, it just moves the storage.
- If you only need the longest symmetric run, do you need the whole table?No. The dependency only reaches the neighbouring row, so two rows suffice and the space drops to O(n). Better still, centre expansion gives the same O(n^2) time in O(1) space. Keep the full table only when something will query arbitrary pairs later.
saying these in an interview costs you the question
- Fills the table row by row and expects correct results
- Says the recurrence reads the cell directly above
- Assumes a wrong fill order will crash or loop forever
- Thinks memoised recursion uses no extra space
- Believes span-length order is the only valid one