LeetCode · #1091

Shortest Path in Binary Matrix Solution

Find the length of the shortest clear path from the top-left cell to the bottom-right cell in a binary matrix. Because every move has equal cost, this is a classic BFS shortest-path problem.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #1091

🏗️

Pattern

Graph — BFS shortest path

You may move in 8 directions, but only through cells containing 0. If either the start or end is blocked, no path exists. Because each move counts as one step, the shortest path length is exactly the first BFS level that reaches the destination.

Example

 Input: grid = [[0,1],[1,0]]
Output: 2 // path: (0,0) → (1,1) using a diagonal move 

Constraints

 • 1 ≤ n ≤ 100 • grid is n × n • grid[i][j] is 0 or 1 

Section Two · Brute Force

Backtracking All Paths — Exponential

A naive idea is to try every possible clear path from the start to the end, track the length, and keep the minimum. That means recursive DFS with backtracking over up to 8 neighbors per cell.

Why it works

If you enumerate every valid path, the minimum length among them is of course the shortest path.

Problem: This is far too expensive because the number of possible paths blows up combinatorially. Worse, shortest-path problems in unweighted graphs have a built-in optimal tool: BFS visits nodes in increasing distance order, so we do not need to explore long paths first.

Java — DFS backtracking sketch

 class Solution {
private static final int[][] DIRS = {
        {-1,-1}, {-1,0}, {-1,1},
        {0,-1},                 {0,1},
        {1,-1},  {1,0},  {1,1}
    };
private int best = Integer.MAX_VALUE;
public int shortestPathBinaryMatrix(int[][] grid) {
if (grid[0][0] == 1 || grid[grid.length - 1][grid.length - 1] == 1)
return -1;
dfs(grid, 0, 0, 1);
return best == Integer.MAX_VALUE ? -1 : best;
    }
private void dfs(int[][] grid, int r, int c, int len) {
int n = grid.length;
if (len >= best) return;
if (r == n - 1 && c == n - 1) { best = len; return; }

        grid[r][c] = 1;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] == 1) continue;
dfs(grid, nr, nc, len + 1);
        }
        grid[r][c] = 0;
    }
}

Python — DFS backtracking sketch

 class Solution:
def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n = len(grid)
if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
return -1
best = [float('inf')]
        dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
def dfs(r: int, c: int, length: int) -> None:
if length >= best[0]:
return if r == n - 1 and c == n - 1:
                best[0] = length
return
grid[r][c] = 1 for dr, dc in dirs:
                nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
dfs(nr, nc, length + 1)
            grid[r][c] = 0 dfs(0, 0, 1)
return -1 if best[0] == float('inf') else best[0]

Section Three · Optimal

BFS by Distance Layers — O(n²)

Treat each clear cell as a graph node. Two nodes share an edge if they are adjacent in one of the 8 directions. Since every edge has equal weight 1, BFS guarantees that the first time we reach a cell, we used the fewest possible moves to get there.

💡 Mental model: Imagine dropping a pebble at the start cell. Ripples spread outward one ring at a time in all 8 directions. The first ripple that touches the destination gives the shortest path length.

Algorithm

If the start or end cell is blocked, return -1 immediately.
Initialize a queue with (0, 0, 1) because the path length counts the starting cell.
When visiting a neighbor, mark it as visited before enqueueing.
If you pop the bottom-right cell, return its path length immediately.
If BFS finishes without reaching the target, no path exists.

🎯 Recognition pattern:

“Shortest path”, “minimum number of moves”, or “fewest steps” on an unweighted grid means BFS.
If the grid edges carried different costs, then you would need Dijkstra instead.

Section Four · Walkthrough

Visual Walkthrough

BFS expands cells in increasing path length

Section Five · Code

Code — Java & Python

Java — BFS shortest path

 import java.util.ArrayDeque;
import java.util.Queue;
class Solution {
private static final int[][] DIRS = {
        {-1,-1}, {-1,0}, {-1,1},
        {0,-1},                 {0,1},
        {1,-1},  {1,0},  {1,1}
    };
public int shortestPathBinaryMatrix(int[][] grid) {
int n = grid.length;
if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;
Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[] { 0, 0, 1 });
        grid[0][0] = 1; // mark visited while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1], dist = cell[2];
if (r == n - 1 && c == n - 1) return dist;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= n || nc < 0 || nc >= n || grid[nr][nc] != 0) continue;
                grid[nr][nc] = 1;
                queue.offer(new int[] { nr, nc, dist + 1 });
            }
        }
return -1;
    }
}

Python — BFS shortest path

 from collections import deque
class Solution:
def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n = len(grid)
if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
return -1
dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
        queue = deque([(0, 0, 1)])
        grid[0][0] = 1 while queue:
            r, c, dist = queue.popleft()
if r == n - 1 and c == n - 1:
return dist
for dr, dc in dirs:
                nr, nc = r + dr, c + dc
if nr < 0 or nr >= n or nc < 0 or nc >= n or grid[nr][nc] != 0:
continue
grid[nr][nc] = 1
queue.append((nr, nc, dist + 1))
return -1 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DFS backtracking	Exponential	O(n²) recursion / visited state	Enumerates too many paths; impractical.
BFS ← optimal	O(n²)	O(n²)	Each cell is enqueued at most once, and BFS returns as soon as the target is first reached.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Expected behavior	Why it matters
Start blocked	Return `-1`	No path can begin.
End blocked	Return `-1`	No path can finish.
Single-cell grid `[[0]]`	Return `1`	The path includes the start cell itself.
Diagonal-only path	Count diagonal moves normally	This problem has 8 directions, unlike many grid BFS questions.
Visited marked too late	Duplicate queue entries	Mark neighbors before enqueueing, not after dequeueing.

⚠ Common Mistake: Returning the number of edges instead of the number of cells in the path. LeetCode 1091 defines the answer as path length in cells, so the starting cell contributes 1, not 0.

← Back to BFS problems

LearningTree

LC 1091 · Shortest Path in Binary Matrix — Solution & Explanation | DSA Guide