Why is grid path backtracking not O(rows x cols) even though visited cells are marked?
answer
- what does a per-cell bound require?
- is the mark permanent or temporary?
- how many different paths reach one cell?
- count starts, then branching, then depth
- four ways out, minus the cell you came from
basics
~20 sThe mark is scoped to one path, not to the whole search, so it is cleared on the way out and the same cell is re-entered by exponentially many different partial paths. The cost is about rows times cols starting points, each exploring roughly 3 to the power of the target length.
solid answer
~50 sA per-cell bound needs each cell to be settled once and never revisited — that is what a reachability sweep gets by marking permanently. Path search cannot: failing on one path says nothing about another, so the mark is cleared on backtrack and the cell is fair game for every other partial path. Counting the work: every cell is tried as a start, giving `rows * cols` roots; the first step branches four ways and every later step at most three, because the cell you came from is on the path; depth is the target's length `L`. That gives `O(rows * cols * 3^L)` time, with `4^L` as the looser bound people often quote, and `O(L)` recursion-stack space plus the visited grid. Big-O here is an upper bound — on real letter grids most branches die within two cells.
go deeper
Be ready to state the shape of the cost: every cell is tried as a start, and from each start the search explores paths as long as the target. That is a product, not a single pass over the grid.
Derive it out loud: rows times columns roots, branching four then three because the came-from cell is on the path, depth equal to the target length, stack space equal to the depth.
Show judgment about the gap between the bound and reality: name the all-one-symbol adversarial grid that realises it, and the linear symbol-count pre-check that rejects impossible targets before any search runs.
Own the risk framing. An exponential worst case behind a request-serving endpoint is an availability question, not a trivia answer — decide whether you cap the target length, pre-filter by symbol counts, or accept the tail, and write that limit into the contract.
## Where the exponential comes from Two quantities multiply. **Starting points.** The search does not know where a match begins, so every cell is tried as a root: `rows * cols` of them, call it `N`. **Paths from one root.** From the root, the path may step to any of four orthogonal neighbours. From every cell after that, one of the four neighbours is the cell you just came from, and it is marked as on-path, so at most **three** extensions survive. The path has as many cells as the target has characters, `L`. So one root explores at most `4 * 3^(L-1)` paths, which is `O(3^L)`. Total: **`O(N * 3^L)` time**. You will also see `O(N * 4^L)` quoted; it is a correct but looser bound that ignores the came-from cell. Either is defensible in an interview as long as you can say which is tighter and why. **Space** is the piece candidates most often get wrong: it is `O(L)` for the recursion stack — the depth of a path, not the size of the grid — plus `O(N)` if you keep a separate visited grid, or `O(1)` extra if you overwrite cells with a sentinel and restore them. Recursion depth is space, and it is bounded by the path length, so a short target on a huge grid uses a shallow stack. ## Why marking does not buy a per-cell bound The intuition behind "marking makes it linear" is real, but it belongs to a different problem. A reachability sweep marks a cell the first time it reaches it and **never clears the mark**, because the question it answers — is this cell connected to the start — is settled the moment the cell is reached. Each cell is expanded once, each of its edges is examined a constant number of times, and the whole sweep is `O(N)`. Path search has no such finality. "This cell is on the path I am currently building" is not a conclusion about the cell; it is a fact about one branch. A cell that dead-ends on the path through its west neighbour may be exactly the cell the path through its north neighbour needs. So the mark is cleared on the way out, and the same cell is entered again by an exponential number of distinct partial paths — one per way of getting there. Put differently: the sweep is a search over **cells** (`N` states). The path search is a search over **paths** (a state is a cell *plus* the set of cells already used), and the number of those states is exponential in `L`. | | reachability sweep | path search | |---|---|---| | state | a cell | a cell plus the path used to reach it | | mark cleared? | never | on backtrack | | bound | O(rows * cols) | O(rows * cols * 3^L) | ## Big-O is an upper bound, and this one is loose A candidate who says `3^L` and stops has answered the question. A candidate who adds what actually happens has answered it well. On a genomics-style grid over a four-letter alphabet, roughly three quarters of the cells fail the very first character comparison, and of the branches that survive, most die within another step or two. The measured behaviour is nearly linear in the number of cells, and the exponential is a statement about what an adversary could construct, not about typical input. The adversarial input is easy to describe and worth being able to name: a grid where every cell holds the **same** symbol and a target made of that symbol repeated. Nothing ever prunes, every branch survives to full depth, and the bound is realised. Interviewers like this because it separates "I memorised the complexity" from "I understand which input drives it". ## Cheap pre-checks the bound does not see Because the exponential is driven by `L` and by how rarely comparisons fail, two constant-or-linear pre-checks pay for themselves enormously: - If the target is longer than `rows * cols`, no simple path can hold it — answer false without searching at all. - Count how many cells hold each symbol once, in `O(N)`, and compare against the target's symbol counts. If the target needs five occurrences of a symbol the grid has three of, no path exists. This kills the all-same-symbol adversarial case in linear time when the counts do not line up, and costs one pass when they do. A related micro-choice: start the search from whichever end of the target is **rarer** in the grid. The search tree is the same shape, but the root loop has far fewer surviving starts, and the first-level branching factor collapses. It changes no asymptotic bound and routinely changes runtime by an order of magnitude — which is the general lesson about `3^L` bounds. They tell you what the worst case permits, not what your grid does.
- Why is the branching factor 3 after the first step rather than 4?Because one of the four orthogonal neighbours is the cell you just came from, and it is marked as being on the current path, so the recursion rejects it immediately. Only the first step has all four open. That gives `4 * 3^(L-1)` paths per root; the frequently quoted `4^L` is the same bound with that refinement dropped.
- What is the space complexity, and what drives it?`O(L)` for the recursion stack, where `L` is the target's length — recursion depth is space, and depth here is the path length, not the grid size. Add `O(rows * cols)` if you keep a separate visited grid, or `O(1)` extra if you overwrite cells with a sentinel and restore them on backtrack.
- Describe an input that actually realises the exponential bound.A grid in which every cell holds the same symbol, searched for a target that is that symbol repeated. No comparison ever fails, so nothing prunes, every branch survives to full depth, and every start contributes its full subtree. On realistic mixed-symbol grids most branches die within two cells and the search behaves close to linear.
- Can memoisation collapse this to a polynomial bound?Not in general. The memo key would have to include the set of cells already used, since the same cell at the same target depth has different answers depending on what the path has consumed — and that set is exponential. Memoisation works on grid problems whose state is just a coordinate and a depth; the no-reuse constraint is exactly what destroys that property.
saying these in an interview costs you the question
- Says visited marking makes the search linear in the cells
- Quotes O(rows x cols) because each cell is marked once
- Gives space as O(rows x cols) for the recursion stack
- Claims the bound describes typical runtime on real grids
- Thinks memoising on the cell alone is sound here