Shortest Path in Binary Matrix (LeetCode 1091)
You get a square grid grid with n rows and n columns. Each cell holds 0 or 1. A cell with 0 is open. A cell with 1 is blocked.
You start in the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, n - 1). In one move, you step to any of the 8 cells around you: up, down, left, right, or one of the 4 diagonals. You may stand only on open cells.
The length of a path is the number of cells on it, and the start cell counts. Return the length of the shortest path. Return -1 when no path exists.
Worked Examples
grid = [[0,1],[1,0]]2(0, 0) to (1, 1). The path has 2 cells.grid = [[0,0,0],[1,1,0],[1,1,0]]4(0, 0), (0, 1), (1, 2), (2, 2). It has 4 cells.grid = [[1,0,0],[1,1,0],[1,1,0]]-1(0, 0) holds 1, so it is blocked and no path exists.⚖️Formal Constraints & Bounds
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j]is 0 or 1
Core Insight
Dijkstra's algorithm pops the state with the lowest cost so far. A* pops the state with the lowest cost so far plus a guess of the cost still to go. When the guess is never larger than the true cost still to go, the first goal that is popped has the lowest cost, and fewer states are popped on the way.
Real-World Scenario & Production Applications
A game character walks across a map made of tiles, and a diagonal step is allowed. The game needs the shortest route to a flag. The flag position is known, so the search can try the tiles that are closer to the flag first.
Step-by-Step Execution Trace Table
Trace of Example 2: grid = [[0,0,0],[1,1,0],[1,1,0]]. Here n = 3 and guess(r, c) = max(2 - r, 2 - c). Each entry of pq is (cost + guess, cost, row, column). pq starts as [(3, 1, 0, 0)], because the start cell has cost = 1 and guess = 2.
| Pop | Entry popped | Cells pushed | pq after the pushes (smallest first) |
|---|---|---|---|
| 1 | (3, 1, 0, 0) | (0, 1) with cost = 2 and total 4 | [(4, 2, 0, 1)] |
| 2 | (4, 2, 0, 1) | (1, 2) with cost = 3 and total 4, (0, 2) with cost = 3 and total 5 | [(4, 3, 1, 2), (5, 3, 0, 2)] |
| 3 | (4, 3, 1, 2) | (2, 2) with cost = 4 and total 4 | [(4, 4, 2, 2), (5, 3, 0, 2)] |
| 4 | (4, 4, 2, 2) | none: this is the bottom-right cell, so return 4 |
The cell (0, 2) is pushed with total 5 and is never popped, because the goal is popped first with total 4.
grid = [[0,1],[1,0]]2Trace of Example 2: grid = [[0,0,0],[1,1,0],[1,1,0]]. Here n = 3 and guess(r, c) = max(2 - r, 2 - c). Each entry of pq is (cost + guess, cost, row, column). pq starts as [(3, 1, 0, 0)], because the start cell has cost = 1 and guess = 2.
| Pop | Entry popped | Cells pushed | pq after the pushes (smallest first) |
|---|---|---|---|
| 1 | (3, 1, 0, 0) | (0, 1) with cost = 2 and total 4 | [(4, 2, 0, 1)] |
| 2 | (4, 2, 0, 1) | (1, 2) with cost = 3 and total 4, (0, 2) with cost = 3 and total 5 | [(4, 3, 1, 2), (5, 3, 0, 2)] |
| 3 | (4, 3, 1, 2) | (2, 2) with cost = 4 and total 4 | [(4, 4, 2, 2), (5, 3, 0, 2)] |
| 4 | (4, 4, 2, 2) | none: this is the bottom-right cell, so return 4 |
The cell (0, 2) is pushed with total 5 and is never popped, because the goal is popped first with total 4.
| 1 | best = {(0, 0): 1} |
| 2 | pq = [(1 + guess(0, 0), 1, 0, 0)] |
| 3 | while pq: |
| 4 | _, cost, r, c = heappop(pq) |
| 5 | if cost > best[(r, c)]: |
| 6 | continue |
| 7 | if (r, c) is the bottom-right cell: |
| 8 | return cost |
| 9 | for each of the 8 neighbours (nr, nc) that is open: |
| 10 | if cost + 1 < best.get((nr, nc), inf): |
| 11 | best[(nr, nc)] = cost + 1 |
| 12 | heappush(pq, (cost + 1 + guess(nr, nc), cost + 1, nr, nc)) |
| 13 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Dijkstra's algorithm pops the state with the lowest cost so far. That search spreads in every direction, like a ring that grows around the start. When you know where the goal is, most of that ring is wasted effort. A* adds one number to each state: a guess of the cost still to go. The heap pops the state with the lowest cost + guess.
🧭 The Guess, Step by Step
On a grid where every move goes to one of 8 neighbours, a cell that still has some rows and some columns to go to the corner needs at least max(rows left, columns left) more moves. A diagonal move lowers both numbers by 1 in one move, so the larger of the two is the best case. That number is never too large. A guess that is never too large is called admissible. This guess is also consistent: one move lowers it by at most 1, and a move costs 1. A consistent guess makes the first pop of a cell final.
🔑 The Key Idea in the Code
Two lines carry the idea. heapq.heappush(pq, (cost + 1 + guess(nr, nc), cost + 1, nr, nc)) orders the heap by cost plus guess. if r == n - 1 and c == n - 1: return cost checks the goal only when it is popped. With guess equal to 0, the same code is Dijkstra's algorithm.
Using a guess that can be larger than the true cost still to go:
(n - 1 - r) + (n - 1 - c)counts a diagonal move twice. On[[0, 0, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]the search returns 7 instead of 6.Skipping the stale check after the pop: a cell can wait in
pqmore than once. The answer stays right, but the older entry expands the cell again.Checking the goal when it is pushed instead of when it is popped: a cheaper way to the goal can still wait in
pqwhen step costs differ.Marking a cell as seen the first time it is pushed: the first way to a cell can be the more expensive one, and a later cheaper way must replace it.
Ordering
pqby the guess alone: the search follows the cell that looks closest to the goal. On[[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 0]]it returns 6 instead of 5.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Shortest clear path" that starts in the top-left corner and ends in the bottom-right corner, with moves to all 8 neighbours. There is one start and one known goal cell, so the rows and columns left give a cheap guess of the moves left. When the goal is one known position and a guess that is never too large exists, A* pops fewer cells than a search that expands in every direction.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Every entry in pq is (cost + guess, cost, r, c), and guess(r, c) = max(n - 1 - r, n - 1 - c) is never larger than the number of cells still to be added to the path. When (n - 1, n - 1) is popped, cost is final, because every other path is still behind an entry whose total is at least as large.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The start cell has
cost = 1, because the path length counts cells. A start of 0 makes every answer one too small.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd solve this with A star search. The start and the goal are two known cells, and a diagonal move is one step, so the moves left from a cell are at least the larger of the rows left and the columns left. That guess is never too large. I keep best, the lowest cost found for each cell, and a min-heap ordered by cost plus guess. I pop the smallest entry and skip it if its cost is higher than best. When I pop the bottom-right cell, its cost is the answer, because every other path is still behind an entry with a total at least as large. If the guess were the rows left plus the columns left, it would count a diagonal move twice and could return a longer path. Time is order N squared times log N, and space is order N squared."
Complexity & Mathematical Proof
O(N^2 log N)
An N x N grid has N^2 cells. The guess is consistent, because one move changes max(n - 1 - r, n - 1 - c) by at most 1, so each cell is expanded once with its final cost. An expansion scans 8 neighbours, which is constant work, and pushes at most 8 entries. So pq receives at most 8 * N^2 entries in all. Each push and pop costs O(log(8 * N^2)), which is O(log N). The total is O(N^2 log N). The guess keeps this bound and usually lowers the number of pops: on an empty grid only the N cells on the diagonal are popped, and with a guess of 0 all N^2 cells are popped.
O(N^2)
best holds one entry for each cell that was reached, at most N^2. pq holds at most 8 * N^2 entries. There is no recursion. The answer is one integer. So the space is O(N^2).
Derivation Progression
The guess is consistent, so a cell popped with cost == best[(r, c)] already has its final cost. Later entries for the cell are skipped as stale.
8 = O(1)
for dr, dc in directions visits 8 neighbours, and each test is constant work.
A push happens only when a neighbour's cost gets lower, at most once for each expansion and neighbour pair. The heap holds at most 8N^2 entries, so log(8N^2) = O(log N).
Expansions times the constant work per expansion, plus the heap work.
Variable Definitions
Side length of the grid, n
The fewest cells found so far on a path from (0, 0) to a cell
max(n - 1 - r, n - 1 - c), the moves still needed at least
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(N^2): best (at most N^2 entries) and pq (at most 8 * N^2 entries)
O(1): one integer
Boundary Best / Worst Cases
on an empty grid: only the N cells on the diagonal are popped.
at most. The guess usually pops fewer cells.
when walls force the search to pop most of the cells.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "shortest clear path", "8-directionally connected". There is one start and one known goal cell, so the rows and columns left give a cheap guess of the moves left, and the search can be ordered by cost + guess.
, so the grid has up to cells. Each expansion scans 8 neighbours and pushes at most 8 entries, so pq receives at most entries. One search is . cost is at most , so 32-bit integers are enough.
A guess of rows left plus columns left counts a diagonal move twice, and [[0, 0, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] returns 7 instead of 6. Ordering pq by guess alone returns 6 instead of 5 on [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 0]]. The start cell counts as 1, and a blocked start or end cell returns -1 before the loop.
Shortest Path in Binary Matrix (LeetCode 1091)
You get a square grid grid with n rows and n columns. Each cell holds 0 or 1. A cell with 0 is open. A cell with 1 is blocked.
You start in the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, n - 1). In one move, you step to any of the 8 cells around you: up, down, left, right, or one of the 4 diagonals. You may stand only on open cells.
The length of a path is the number of cells on it, and the start cell counts. Return the length of the shortest path. Return -1 when no path exists.
Worked Examples
grid = [[0,1],[1,0]]2(0, 0) to (1, 1). The path has 2 cells.grid = [[0,0,0],[1,1,0],[1,1,0]]4(0, 0), (0, 1), (1, 2), (2, 2). It has 4 cells.grid = [[1,0,0],[1,1,0],[1,1,0]]-1(0, 0) holds 1, so it is blocked and no path exists.⚖️Formal Constraints & Bounds
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j]is 0 or 1
Core Insight
Dijkstra's algorithm pops the state with the lowest cost so far. A* pops the state with the lowest cost so far plus a guess of the cost still to go. When the guess is never larger than the true cost still to go, the first goal that is popped has the lowest cost, and fewer states are popped on the way.
Real-World Scenario & Production Applications
A game character walks across a map made of tiles, and a diagonal step is allowed. The game needs the shortest route to a flag. The flag position is known, so the search can try the tiles that are closer to the flag first.
Step-by-Step Execution Trace Table
Trace of Example 2: grid = [[0,0,0],[1,1,0],[1,1,0]]. Here n = 3 and guess(r, c) = max(2 - r, 2 - c). Each entry of pq is (cost + guess, cost, row, column). pq starts as [(3, 1, 0, 0)], because the start cell has cost = 1 and guess = 2.
| Pop | Entry popped | Cells pushed | pq after the pushes (smallest first) |
|---|---|---|---|
| 1 | (3, 1, 0, 0) | (0, 1) with cost = 2 and total 4 | [(4, 2, 0, 1)] |
| 2 | (4, 2, 0, 1) | (1, 2) with cost = 3 and total 4, (0, 2) with cost = 3 and total 5 | [(4, 3, 1, 2), (5, 3, 0, 2)] |
| 3 | (4, 3, 1, 2) | (2, 2) with cost = 4 and total 4 | [(4, 4, 2, 2), (5, 3, 0, 2)] |
| 4 | (4, 4, 2, 2) | none: this is the bottom-right cell, so return 4 |
The cell (0, 2) is pushed with total 5 and is never popped, because the goal is popped first with total 4.
grid = [[0,1],[1,0]]2Trace of Example 2: grid = [[0,0,0],[1,1,0],[1,1,0]]. Here n = 3 and guess(r, c) = max(2 - r, 2 - c). Each entry of pq is (cost + guess, cost, row, column). pq starts as [(3, 1, 0, 0)], because the start cell has cost = 1 and guess = 2.
| Pop | Entry popped | Cells pushed | pq after the pushes (smallest first) |
|---|---|---|---|
| 1 | (3, 1, 0, 0) | (0, 1) with cost = 2 and total 4 | [(4, 2, 0, 1)] |
| 2 | (4, 2, 0, 1) | (1, 2) with cost = 3 and total 4, (0, 2) with cost = 3 and total 5 | [(4, 3, 1, 2), (5, 3, 0, 2)] |
| 3 | (4, 3, 1, 2) | (2, 2) with cost = 4 and total 4 | [(4, 4, 2, 2), (5, 3, 0, 2)] |
| 4 | (4, 4, 2, 2) | none: this is the bottom-right cell, so return 4 |
The cell (0, 2) is pushed with total 5 and is never popped, because the goal is popped first with total 4.
| 1 | best = {(0, 0): 1} |
| 2 | pq = [(1 + guess(0, 0), 1, 0, 0)] |
| 3 | while pq: |
| 4 | _, cost, r, c = heappop(pq) |
| 5 | if cost > best[(r, c)]: |
| 6 | continue |
| 7 | if (r, c) is the bottom-right cell: |
| 8 | return cost |
| 9 | for each of the 8 neighbours (nr, nc) that is open: |
| 10 | if cost + 1 < best.get((nr, nc), inf): |
| 11 | best[(nr, nc)] = cost + 1 |
| 12 | heappush(pq, (cost + 1 + guess(nr, nc), cost + 1, nr, nc)) |
| 13 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Dijkstra's algorithm pops the state with the lowest cost so far. That search spreads in every direction, like a ring that grows around the start. When you know where the goal is, most of that ring is wasted effort. A* adds one number to each state: a guess of the cost still to go. The heap pops the state with the lowest cost + guess.
🧭 The Guess, Step by Step
On a grid where every move goes to one of 8 neighbours, a cell that still has some rows and some columns to go to the corner needs at least max(rows left, columns left) more moves. A diagonal move lowers both numbers by 1 in one move, so the larger of the two is the best case. That number is never too large. A guess that is never too large is called admissible. This guess is also consistent: one move lowers it by at most 1, and a move costs 1. A consistent guess makes the first pop of a cell final.
🔑 The Key Idea in the Code
Two lines carry the idea. heapq.heappush(pq, (cost + 1 + guess(nr, nc), cost + 1, nr, nc)) orders the heap by cost plus guess. if r == n - 1 and c == n - 1: return cost checks the goal only when it is popped. With guess equal to 0, the same code is Dijkstra's algorithm.
Using a guess that can be larger than the true cost still to go:
(n - 1 - r) + (n - 1 - c)counts a diagonal move twice. On[[0, 0, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]the search returns 7 instead of 6.Skipping the stale check after the pop: a cell can wait in
pqmore than once. The answer stays right, but the older entry expands the cell again.Checking the goal when it is pushed instead of when it is popped: a cheaper way to the goal can still wait in
pqwhen step costs differ.Marking a cell as seen the first time it is pushed: the first way to a cell can be the more expensive one, and a later cheaper way must replace it.
Ordering
pqby the guess alone: the search follows the cell that looks closest to the goal. On[[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 0]]it returns 6 instead of 5.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Shortest clear path" that starts in the top-left corner and ends in the bottom-right corner, with moves to all 8 neighbours. There is one start and one known goal cell, so the rows and columns left give a cheap guess of the moves left. When the goal is one known position and a guess that is never too large exists, A* pops fewer cells than a search that expands in every direction.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Every entry in pq is (cost + guess, cost, r, c), and guess(r, c) = max(n - 1 - r, n - 1 - c) is never larger than the number of cells still to be added to the path. When (n - 1, n - 1) is popped, cost is final, because every other path is still behind an entry whose total is at least as large.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The start cell has
cost = 1, because the path length counts cells. A start of 0 makes every answer one too small.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd solve this with A star search. The start and the goal are two known cells, and a diagonal move is one step, so the moves left from a cell are at least the larger of the rows left and the columns left. That guess is never too large. I keep best, the lowest cost found for each cell, and a min-heap ordered by cost plus guess. I pop the smallest entry and skip it if its cost is higher than best. When I pop the bottom-right cell, its cost is the answer, because every other path is still behind an entry with a total at least as large. If the guess were the rows left plus the columns left, it would count a diagonal move twice and could return a longer path. Time is order N squared times log N, and space is order N squared."
Complexity & Mathematical Proof
O(N^2 log N)
An N x N grid has N^2 cells. The guess is consistent, because one move changes max(n - 1 - r, n - 1 - c) by at most 1, so each cell is expanded once with its final cost. An expansion scans 8 neighbours, which is constant work, and pushes at most 8 entries. So pq receives at most 8 * N^2 entries in all. Each push and pop costs O(log(8 * N^2)), which is O(log N). The total is O(N^2 log N). The guess keeps this bound and usually lowers the number of pops: on an empty grid only the N cells on the diagonal are popped, and with a guess of 0 all N^2 cells are popped.
O(N^2)
best holds one entry for each cell that was reached, at most N^2. pq holds at most 8 * N^2 entries. There is no recursion. The answer is one integer. So the space is O(N^2).
Derivation Progression
The guess is consistent, so a cell popped with cost == best[(r, c)] already has its final cost. Later entries for the cell are skipped as stale.
8 = O(1)
for dr, dc in directions visits 8 neighbours, and each test is constant work.
A push happens only when a neighbour's cost gets lower, at most once for each expansion and neighbour pair. The heap holds at most 8N^2 entries, so log(8N^2) = O(log N).
Expansions times the constant work per expansion, plus the heap work.
Variable Definitions
Side length of the grid, n
The fewest cells found so far on a path from (0, 0) to a cell
max(n - 1 - r, n - 1 - c), the moves still needed at least
Memory Architecture & Bounds
O(1): a loop only, no recursion
O(N^2): best (at most N^2 entries) and pq (at most 8 * N^2 entries)
O(1): one integer
Boundary Best / Worst Cases
on an empty grid: only the N cells on the diagonal are popped.
at most. The guess usually pops fewer cells.
when walls force the search to pop most of the cells.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "shortest clear path", "8-directionally connected". There is one start and one known goal cell, so the rows and columns left give a cheap guess of the moves left, and the search can be ordered by cost + guess.
, so the grid has up to cells. Each expansion scans 8 neighbours and pushes at most 8 entries, so pq receives at most entries. One search is . cost is at most , so 32-bit integers are enough.
A guess of rows left plus columns left counts a diagonal move twice, and [[0, 0, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]] returns 7 instead of 6. Ordering pq by guess alone returns 6 instead of 5 on [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 0]]. The start cell counts as 1, and a blocked start or end cell returns -1 before the loop.