In a warehouse grid with blocked aisles, why can't the whole top row be seeded with 1 route?
answer
- what does the seed value 1 assert
- one blocked aisle in the top row
- reachability, not merely existence
- zero has to propagate along the border
- seed only the start, let the rule run
basics
~20 sA blocked cell in the top row cuts the row: every cell past it is unreachable and must hold 0, not 1. The same applies down the left column, and a blocked start cell makes the whole answer 0.
solid answer
~40 sThe seed value 1 encodes a claim — "there is exactly one straight-line approach along the border" — and a block anywhere earlier in that border falsifies it for every cell after it. So the top row must stop at the first block and hold 0 from there on, and likewise the left column. The robust fix is to stop writing border code at all: mark blocked cells 0, seed only the start cell (1 if it is clear), and run the single recurrence over every cell with any off-grid read treated as 0. Border cells then derive their value from their one in-grid predecessor automatically, and the degenerate inputs — blocked start, blocked destination, a fully blocked row, a single-row floor — all fall out correctly with no special cases to remember.
code
pseudocode · 12 linesroutes[0][0] = 1
for j in 1..n-1:
routes[0][j] = 1
for i in 1..m-1:
routes[i][0] = 1
for i in 1..m-1:
for j in 1..n-1:
if blocked[i][j]:
routes[i][j] = 0
else:
routes[i][j] = routes[i-1][j] + routes[i][j-1]
answer = routes[m-1][n-1]go deeper
Be ready to trace a small floor plan with one blocked cell in the top row by hand and point to exactly which cells become 0 as a result.
Expect to be asked to restructure the code so the border is not a special case, and to name the degenerate inputs — blocked start, blocked destination, fully blocked row — that break naive seeding.
Demonstrate that you reach for the boundary tests first. These four inputs are what ship broken, and the uniform recurrence is a maintainability argument as much as a correctness one.
The call to own is where reachability is enforced. One guarded rule that every cell obeys costs less over a codebase's life than three seeding loops each future edit must remember to keep in sync.
## What the seed value actually asserts On an open grid, seeding the top row and left column with 1 is a shortcut for a fact, not a convention: there is exactly one way to reach any border cell, by driving straight along the border. Introduce blocked aisles and that fact stops being true. If the third cell of the top row is blocked, then cells four, five and six of that row have no approach at all from the left, and none from above because there is no row above. Their true count is 0. A seeding loop that writes 1 across the whole row asserts reachability that the floor plan denies, and the interior sweep never corrects it — it only ever adds the border's numbers into the interior, so one bad seed silently inflates the final answer. ## The buggy shape The classic broken version has three separate loops: seed the top row, seed the left column, then sweep the interior with a blocked check. The blocked check appears only in the third loop. Every block on the border is therefore ignored, and every block on the border is exactly where the damage propagates furthest, because the entire remainder of that border feeds the interior. ## Two correct formulations **Patched border.** Walk the top row left to right and write 1 until you hit a block; write 0 from the block onward. Do the same down the left column. This works and is easy to say out loud, but it leaves three places where a future edit must remember the blocked rule. **Uniform recurrence.** Better: keep exactly one rule. Set `routes[0][0] = 1` if the start cell is clear, otherwise 0. Then sweep every cell in order; if the cell is blocked write 0, otherwise write the sum of the cell above and the cell to the left, where any read that falls off the grid contributes 0. The border is no longer a special case at all — a top-row cell simply has one contributing predecessor because the other is off-grid, and a top-row cell after a block gets `0 + 0`. Zero propagates for free, which is precisely the behaviour the patched version has to be told about explicitly. ## The degenerate inputs that decide the interview These are the cases an interviewer probes, and the uniform formulation handles all four without extra code: | Input | Correct answer | What the naive seeding does | |---|---|---| | Start cell blocked | 0 | Returns a positive count from a seed of 1 | | Destination blocked | 0 | Correct only if the blocked check runs on that cell | | Entire top row blocked after column 1 | counts from the left column only | Inflates by counting phantom top-row approaches | | Single-row floor with one block | 0 | Returns 1 | The blocked-start case is the one candidates most often miss, because it is the only case where the very first line of the algorithm is the bug. ## Complexity is unchanged All of this is still `O(m*n)` time and `O(m*n)` space — or `O(n)` space with a rolling row. Blocked cells make the problem no harder asymptotically; they make it harder to get *right*, which is why interviewers use them. Nothing about the fill order changes either: each cell still depends only on cells already computed in a left-to-right, row-by-row sweep. ## The same trap in the cost variant When the grid carries per-cell costs and the question becomes "cheapest route", the identical seeding trap appears in a new costume. The border can no longer repeat one value; it must accumulate a running total of costs along the border. And a blocked cell needs a value meaning *unreachable* that no minimum will ever prefer. The tempting move is an enormous sentinel number, which then gets a cost added to it on the next cell and can wrap around into a small number — turning the unreachable cell into the most attractive route on the floor. The safe version tests reachability explicitly instead of relying on arithmetic with a huge magic number, or carries a separate reachable flag alongside the cost. ## What to say when asked State the invariant the seed encodes, show that a block breaks it, then propose the uniform recurrence and name the four degenerate inputs you would test first. That sequence — invariant, counterexample, fix, boundary tests — is what separates an engineer who has debugged this from one who has memorized a template.
- How would you rewrite this so the border needs no special case at all?Set the start cell to 1 if it is clear and 0 otherwise, then run one loop over every cell: blocked cells write 0, others write the sum of the above and left neighbours with any off-grid read counted as 0. Border cells then take their value from their single in-grid predecessor, and a block anywhere makes 0 propagate on its own.
- What should the result be if the destination cell itself is blocked?Zero, and the uniform formulation gives it for free because the blocked test runs before the sum on every cell including the last one. Hand-written border code often checks blocks only in the interior sweep and returns whatever the last computed value happened to be.
- Does the same trap appear in the minimum-cost version of this grid?Yes, in two ways. The border must accumulate a running sum of costs rather than repeat one value, and blocked cells need a value meaning unreachable. Using an enormous sentinel and then adding a cost to it can wrap around and make the unreachable cell look cheapest, so test reachability explicitly instead of doing arithmetic on a magic number.
saying these in an interview costs you the question
- Seeds every top-row cell to 1 regardless of blocks
- Tests for blocked cells only inside the interior loop
- Returns a positive count when the start cell is blocked
- Forgets that a blocked destination forces the answer to 0
- Adds costs to a huge unreachable sentinel and lets it wrap