Shortest Path in Binary Matrix (LeetCode 1091)
You're given an n x n binary grid. Starting at corner cell (0, 0) and finishing at the opposite corner (n - 1, n - 1), find the shortest clear path between them, or report -1 if no such path exists.
A path counts as clear when every cell it visits holds 0, and each consecutive pair of cells touches 8-directionally — sharing a side or merely a corner both count as touching.
A clear path's length is simply how many cells it visits, start to finish.
Worked Examples
grid = [[0,1],[1,0]]2(0,0) to (1,1): the path visits 2 cells.grid = [[0,0,0],[1,1,0],[1,1,0]]4(0,0) -> (0,1) -> (1,2) -> (2,2) visits 4 cells.grid = [[1,0,0],[1,1,0],[1,1,0]]-1(0,0) holds 1, so no clear path exists.⚖️Formal Constraints & Bounds
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j] is 0 or 1
Core Insight
BFS guarantees shortest path in unweighted graphs because nodes are discovered by wavefront distance.
Real-World Scenario & Production Applications
Robot path planning in obstacle grids and video game character navigation (navmesh traversal).
Step-by-Step Execution Trace Table
Target Path (8-Directional Diagonal Shortcuts):(0,0) [dist=1] ➔ (0,1) [dist=2] ➔ (1,2) [dist=3] ➔ (2,2) [dist=4] ✅ Grid Layout (0=clear, 1=blocked):[ 0 ] [ 0 ] [ 0 ] [ 1 ] [ 2 ] [ . ][ 1 ] [ 1 ] [ 0 ] ==> [ X ] [ X ] [ 3 ][ 1 ] [ 1 ] [ 0 ] [ X ] [ X ] [ 4 ] Step-by-Step Wavefront Progression
- Step 1 (Start Verification & Seed, Hop 1, d=1): Check
grid[0][0] == 0(valid).queue = [(0, 0, 1)]. Mark visited:grid[0][0] = 1. Initial distance is 1. - Step 2 (Dequeue (0,0), Explore 8 Directions, d=1): Pop
(0, 0, dist=1). Explore 8 neighbors: only(0, 1)is clear (others are blocked1or out of bounds). Markgrid[0][1] = 1.queue = [(0, 1, 2)]🌊. - Step 3 (Dequeue (0,1), Diagonal Hop to (1,2), d=2): Pop
(0, 1, dist=2). Explore 8 neighbors: diagonal neighbor(1, 2)and right neighbor(0, 2)are clear. Mark both visitedqueue = [(0, 2, 3), (1, 2, 3)]🌊. - Step 4 (Dequeue (0,2), Path Exploration, d=3): Pop
(0, 2, dist=3). Neighbor(1, 2)is already marked skip. - Step 5 (Dequeue (1,2), Step Down to Target (2,2), d=3): Pop
(1, 2, dist=3). Explore neighbor(2, 2): target(n-1, n-1)discovered! Mark visited and enqueue(2, 2, 4)queue = [(2, 2, 4)]🌊. - Step 6 (Dequeue (2,2), Target Reached, Minimal Path Found, d=4): Pop
(2, 2, dist=4). Goal reached at(2, 2)! First arrival is strictly minimal in unweighted graph. Search Complete: return4✅.
grid = [[0,1],[1,0]]Expected:2| 1 | if grid[0][0] != 0 or grid[-1][-1] != 0: |
| 2 | return -1 |
| 3 | queue = deque([(0, 0, 1)]) |
| 4 | grid[0][0] = 1 |
| 5 | while queue: |
| 6 | r, c, dist = queue.popleft() |
| 7 | if (r, c) == target: |
| 8 | return dist |
| 9 | for each of the 8 neighbors (nr, nc): |
| 10 | if (nr, nc) is inside the grid and grid[nr][nc] == 0: |
| 11 | grid[nr][nc] = 1 |
| 12 | queue.append((nr, nc, dist + 1)) |
| 13 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the shortest path in an unweighted grid from top-left to bottom-right is an exact match for Breadth-First Search. In a binary matrix with 8-directional movement (horizontal, vertical, and diagonal), every move between adjacent open cells (value 0) has an identical edge weight of 1. Because edge weights are uniform, Dijkstra's algorithm is unnecessary; the first moment BFS pops or enqueues the coordinate , the distance traveled is mathematically guaranteed to be the absolute minimum.
🏟️ The Analogy: A Fire Spreading Through Dry Grass
Imagine an empty field covered in dry grass (cells with value 0), interspersed with non-flammable boulders (cells with value 1). You light a match at coordinate . The fire spreads in all 8 directions at a uniform speed of 1 meter per second. The burning perimeter expands outward as a square wavefront. The exact second the fire reaches the target flagpole at , you stop your stopwatch. It is physically impossible for any other flame path to reach the flagpole faster.
🔑 Why It Works
The crucial invariant is marking visited on enqueue: by setting grid[nr][nc] = 1 the instant the cell is added to the queue, you prevent multiple parents from pushing the same unvisited cell, stopping exponential queue explosion and keeping runtime strictly .
4-directional vs 8-directional exploration: Problem permits moving in 8 directions (including diagonals); using only 4 orthogonal directions misses shorter diagonal paths.
Blocked start or end cell: Forgetting to check
if grid[0][0] == 1 or grid[n-1][n-1] == 1: return -1before launching BFS.Marking visited on pop instead of push: Waiting to mark
grid[r][c] = 1until cells are popped causes exponential duplicate enqueuing, resulting in Memory Limit Exceeded.Reaching for BFS on Weighted Graphs: BFS's first-arrival guarantee assumes uniform edge weights. If edge weights vary, a two-hop path with small weights can be shorter than a single-hop heavy edge. Use Dijkstra instead.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Find the "shortest clear path" from (0, 0) to (n - 1, n - 1), where each step moves "8-directionally" and every step counts the same (length is "how many cells it visits"). Fewest equal-cost moves on a grid: Shortest-Path BFS.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Cells leave queue in non-decreasing order of dist, and a cell is marked 1 the moment it is first reached, which is by a shortest path. The decision: push (nr, nc, dist + 1) only when grid[nr][nc] == 0, and return dist the first time (n - 1, n - 1) is popped.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if grid[0][0] != 0 or grid[n - 1][n - 1] != 0: return -1: a blocked corner means no clear path, and nothing else in the loop tests the start cell.grid[nr][nc] = 1right beforequeue.append: the card's trap. Marking only at pop lets every neighbour of a cell push it again; on an open grid the queue grows from 32 pushes at n = 3 to over 375,000 at n = 12.queue = deque([(0, 0, 1)]): length counts cells, so the start is 1, not 0; a 1 x 1 grid[[0]]returns 1.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Shortest-Path BFS. Every step to one of the eight neighbours costs the same, so the fewest cells on a path is a BFS distance. If either corner is blocked I return minus one right away. Otherwise I push the start with distance one, since length counts cells, and mark it. BFS pops cells in order of distance, so the first time I pop the bottom-right corner, its distance is the shortest: any shorter path would have been popped earlier. For each popped cell I check the eight neighbours, and every open one gets marked and pushed with distance plus one. The trap is marking too late: if I only mark a cell when I pop it, all its neighbours can push it again, and the queue fills with copies. Each cell is pushed at most once, so it's O(N squared) time and space for an N by N grid.
Complexity & Mathematical Proof
O(N^2)
Look at the code: a cell is pushed only when grid[nr][nc] == 0, and it is set to 1 in the same step, so each of the N^2 cells is pushed at most once and while queue pops at most N^2 times. Each pop runs for dr, dc in directions over 8 offsets with O(1) work. At most 8 · N^2 checks: O(N^2).
O(N^2)
queue holds at most N^2 entries (r, c, dist). Cells are marked by writing into grid, so no separate visited set; no recursion (call stack O(1)); the answer is one integer.
T(N) ≤ N^2 pops · 8 directions = 8 · N^2 = O(N^2)
Derivation Progression
if ... grid[nr][nc] == 0: grid[nr][nc] = 1; queue.append((nr, nc, dist + 1)) → ≤ N^2 pushes
A cell is pushed only while it is 0 and becomes 1 in the same step, so it can be pushed once.
for dr, dc in directions → 8 checks
Each check is a bounds test and one grid read, O(1).
≤ 8 · N^2 = O(N^2)
At most N^2 pops times 8 checks; the early return dist can only make it smaller.
Variable Definitions
Side of the N × N grid
Memory Architecture & Bounds
O(1): no recursion
O(N^2): queue; visited marks live in grid itself
O(1): the path length
Boundary Best / Worst Cases
when a corner is blocked (return -1 before the loop)
when BFS explores the whole grid
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "shortest clear path", "8-directionally", length = "how many cells it visits": fewest equal-cost moves, Shortest-Path BFS. At scale the same wave expansion finds shortest routes on any uniform-cost grid, where memory, not time, is usually the limit.
cells, 8 neighbours each: at most checks.
Changing grid in place is fine on LeetCode but not for a shared map that other requests read at the same time: keep a separate bitset per search. The early return at the target is what keeps a single query cheap; without it every search explores the whole reachable grid.
Core Algorithmic State Invariants
- Testing the Target at Push Time Also Works
Since a cell's distance is final when it is pushed, returning dist + 1 as soon as (n - 1, n - 1) is pushed gives the same answer one level earlier. Testing at pop is simpler because it also covers the start being the target, [[0]].
Shortest Path in Binary Matrix (LeetCode 1091)
You're given an n x n binary grid. Starting at corner cell (0, 0) and finishing at the opposite corner (n - 1, n - 1), find the shortest clear path between them, or report -1 if no such path exists.
A path counts as clear when every cell it visits holds 0, and each consecutive pair of cells touches 8-directionally — sharing a side or merely a corner both count as touching.
A clear path's length is simply how many cells it visits, start to finish.
Worked Examples
grid = [[0,1],[1,0]]2(0,0) to (1,1): the path visits 2 cells.grid = [[0,0,0],[1,1,0],[1,1,0]]4(0,0) -> (0,1) -> (1,2) -> (2,2) visits 4 cells.grid = [[1,0,0],[1,1,0],[1,1,0]]-1(0,0) holds 1, so no clear path exists.⚖️Formal Constraints & Bounds
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j] is 0 or 1
Core Insight
BFS guarantees shortest path in unweighted graphs because nodes are discovered by wavefront distance.
Real-World Scenario & Production Applications
Robot path planning in obstacle grids and video game character navigation (navmesh traversal).
Step-by-Step Execution Trace Table
Target Path (8-Directional Diagonal Shortcuts):(0,0) [dist=1] ➔ (0,1) [dist=2] ➔ (1,2) [dist=3] ➔ (2,2) [dist=4] ✅ Grid Layout (0=clear, 1=blocked):[ 0 ] [ 0 ] [ 0 ] [ 1 ] [ 2 ] [ . ][ 1 ] [ 1 ] [ 0 ] ==> [ X ] [ X ] [ 3 ][ 1 ] [ 1 ] [ 0 ] [ X ] [ X ] [ 4 ] Step-by-Step Wavefront Progression
- Step 1 (Start Verification & Seed, Hop 1, d=1): Check
grid[0][0] == 0(valid).queue = [(0, 0, 1)]. Mark visited:grid[0][0] = 1. Initial distance is 1. - Step 2 (Dequeue (0,0), Explore 8 Directions, d=1): Pop
(0, 0, dist=1). Explore 8 neighbors: only(0, 1)is clear (others are blocked1or out of bounds). Markgrid[0][1] = 1.queue = [(0, 1, 2)]🌊. - Step 3 (Dequeue (0,1), Diagonal Hop to (1,2), d=2): Pop
(0, 1, dist=2). Explore 8 neighbors: diagonal neighbor(1, 2)and right neighbor(0, 2)are clear. Mark both visitedqueue = [(0, 2, 3), (1, 2, 3)]🌊. - Step 4 (Dequeue (0,2), Path Exploration, d=3): Pop
(0, 2, dist=3). Neighbor(1, 2)is already marked skip. - Step 5 (Dequeue (1,2), Step Down to Target (2,2), d=3): Pop
(1, 2, dist=3). Explore neighbor(2, 2): target(n-1, n-1)discovered! Mark visited and enqueue(2, 2, 4)queue = [(2, 2, 4)]🌊. - Step 6 (Dequeue (2,2), Target Reached, Minimal Path Found, d=4): Pop
(2, 2, dist=4). Goal reached at(2, 2)! First arrival is strictly minimal in unweighted graph. Search Complete: return4✅.
grid = [[0,1],[1,0]]Expected:2| 1 | if grid[0][0] != 0 or grid[-1][-1] != 0: |
| 2 | return -1 |
| 3 | queue = deque([(0, 0, 1)]) |
| 4 | grid[0][0] = 1 |
| 5 | while queue: |
| 6 | r, c, dist = queue.popleft() |
| 7 | if (r, c) == target: |
| 8 | return dist |
| 9 | for each of the 8 neighbors (nr, nc): |
| 10 | if (nr, nc) is inside the grid and grid[nr][nc] == 0: |
| 11 | grid[nr][nc] = 1 |
| 12 | queue.append((nr, nc, dist + 1)) |
| 13 | return -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Finding the shortest path in an unweighted grid from top-left to bottom-right is an exact match for Breadth-First Search. In a binary matrix with 8-directional movement (horizontal, vertical, and diagonal), every move between adjacent open cells (value 0) has an identical edge weight of 1. Because edge weights are uniform, Dijkstra's algorithm is unnecessary; the first moment BFS pops or enqueues the coordinate , the distance traveled is mathematically guaranteed to be the absolute minimum.
🏟️ The Analogy: A Fire Spreading Through Dry Grass
Imagine an empty field covered in dry grass (cells with value 0), interspersed with non-flammable boulders (cells with value 1). You light a match at coordinate . The fire spreads in all 8 directions at a uniform speed of 1 meter per second. The burning perimeter expands outward as a square wavefront. The exact second the fire reaches the target flagpole at , you stop your stopwatch. It is physically impossible for any other flame path to reach the flagpole faster.
🔑 Why It Works
The crucial invariant is marking visited on enqueue: by setting grid[nr][nc] = 1 the instant the cell is added to the queue, you prevent multiple parents from pushing the same unvisited cell, stopping exponential queue explosion and keeping runtime strictly .
4-directional vs 8-directional exploration: Problem permits moving in 8 directions (including diagonals); using only 4 orthogonal directions misses shorter diagonal paths.
Blocked start or end cell: Forgetting to check
if grid[0][0] == 1 or grid[n-1][n-1] == 1: return -1before launching BFS.Marking visited on pop instead of push: Waiting to mark
grid[r][c] = 1until cells are popped causes exponential duplicate enqueuing, resulting in Memory Limit Exceeded.Reaching for BFS on Weighted Graphs: BFS's first-arrival guarantee assumes uniform edge weights. If edge weights vary, a two-hop path with small weights can be shorter than a single-hop heavy edge. Use Dijkstra instead.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Find the "shortest clear path" from (0, 0) to (n - 1, n - 1), where each step moves "8-directionally" and every step counts the same (length is "how many cells it visits"). Fewest equal-cost moves on a grid: Shortest-Path BFS.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Cells leave queue in non-decreasing order of dist, and a cell is marked 1 the moment it is first reached, which is by a shortest path. The decision: push (nr, nc, dist + 1) only when grid[nr][nc] == 0, and return dist the first time (n - 1, n - 1) is popped.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
if grid[0][0] != 0 or grid[n - 1][n - 1] != 0: return -1: a blocked corner means no clear path, and nothing else in the loop tests the start cell.grid[nr][nc] = 1right beforequeue.append: the card's trap. Marking only at pop lets every neighbour of a cell push it again; on an open grid the queue grows from 32 pushes at n = 3 to over 375,000 at n = 12.queue = deque([(0, 0, 1)]): length counts cells, so the start is 1, not 0; a 1 x 1 grid[[0]]returns 1.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Shortest-Path BFS. Every step to one of the eight neighbours costs the same, so the fewest cells on a path is a BFS distance. If either corner is blocked I return minus one right away. Otherwise I push the start with distance one, since length counts cells, and mark it. BFS pops cells in order of distance, so the first time I pop the bottom-right corner, its distance is the shortest: any shorter path would have been popped earlier. For each popped cell I check the eight neighbours, and every open one gets marked and pushed with distance plus one. The trap is marking too late: if I only mark a cell when I pop it, all its neighbours can push it again, and the queue fills with copies. Each cell is pushed at most once, so it's O(N squared) time and space for an N by N grid.
Complexity & Mathematical Proof
O(N^2)
Look at the code: a cell is pushed only when grid[nr][nc] == 0, and it is set to 1 in the same step, so each of the N^2 cells is pushed at most once and while queue pops at most N^2 times. Each pop runs for dr, dc in directions over 8 offsets with O(1) work. At most 8 · N^2 checks: O(N^2).
O(N^2)
queue holds at most N^2 entries (r, c, dist). Cells are marked by writing into grid, so no separate visited set; no recursion (call stack O(1)); the answer is one integer.
T(N) ≤ N^2 pops · 8 directions = 8 · N^2 = O(N^2)
Derivation Progression
if ... grid[nr][nc] == 0: grid[nr][nc] = 1; queue.append((nr, nc, dist + 1)) → ≤ N^2 pushes
A cell is pushed only while it is 0 and becomes 1 in the same step, so it can be pushed once.
for dr, dc in directions → 8 checks
Each check is a bounds test and one grid read, O(1).
≤ 8 · N^2 = O(N^2)
At most N^2 pops times 8 checks; the early return dist can only make it smaller.
Variable Definitions
Side of the N × N grid
Memory Architecture & Bounds
O(1): no recursion
O(N^2): queue; visited marks live in grid itself
O(1): the path length
Boundary Best / Worst Cases
when a corner is blocked (return -1 before the loop)
when BFS explores the whole grid
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "shortest clear path", "8-directionally", length = "how many cells it visits": fewest equal-cost moves, Shortest-Path BFS. At scale the same wave expansion finds shortest routes on any uniform-cost grid, where memory, not time, is usually the limit.
cells, 8 neighbours each: at most checks.
Changing grid in place is fine on LeetCode but not for a shared map that other requests read at the same time: keep a separate bitset per search. The early return at the target is what keeps a single query cheap; without it every search explores the whole reachable grid.
Core Algorithmic State Invariants
- Testing the Target at Push Time Also Works
Since a cell's distance is final when it is pushed, returning dist + 1 as soon as (n - 1, n - 1) is pushed gives the same answer one level earlier. Testing at pop is simpler because it also covers the start being the target, [[0]].