Skip to main content

1091 - Shortest Path in Binary Matrix

Difficulty: Medium | Pattern: BFS on Grid | Company tags: Amazon, Facebook, Uber, Bloomberg

Problem Statement​

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.

A clear path in a binary matrix is a path from the top-left cell (0,0) to the bottom-right cell (n-1,n-1) such that:

  • All visited cells of the path are 0.
  • All adjacent cells of the path are 8-directionally connected (can move diagonally).

The length of a clear path is the number of visited cells.

Example 1:

Input: [[0,1],[1,0]]
Output: 2  (path: (0,0) → (1,1))

Example 2:

Input: [[0,0,0],[1,1,0],[1,1,0]]
Output: 4

Approach: BFS — O(n²)​

Key insight: BFS gives the shortest path in an unweighted graph. Start at (0,0), explore all 8 directions. Track visited by setting cells to 1.

Algorithm Flow​

from collections import deque

def shortestPathBinaryMatrix(grid: list[list[int]]) -> int:
    n = len(grid)
    
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
    
    if n == 1:
        return 1
    
    queue = deque([(0, 0, 1)])  # (row, col, path_length)
    grid[0][0] = 1  # mark visited
    
    directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    
    while queue:
        r, c, length = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                if nr == n-1 and nc == n-1:
                    return length + 1
                grid[nr][nc] = 1  # mark visited
                queue.append((nr, nc, length + 1))
    
    return -1

Dry Run​

grid = [[0,0,0],[1,1,0],[1,1,0]] (3×3)

BFS from (0,0):

  • Length 1: (0,0) start
  • Explore from (0,0): (0,1)=0 → queue; (1,1)=1 skip; (1,0)=1 skip...
  • Length 2: (0,1)
  • Explore from (0,1): (0,2)=0 → queue; (1,2)=0 → queue
  • Length 3: (0,2), (1,2)
  • From (1,2): (2,2) = bottom-right → return 3+1 = 4 ✓

Edge Cases​

  • grid[0][0] = 1 or grid[n-1][n-1] = 1 → return -1 immediately
  • n = 1 and grid[0][0] = 0 → return 1 (already at destination)
  • No path → return -1

Complexity​

  • Time: O(n²) — each cell visited at most once
  • Space: O(n²) — BFS queue

Note: BFS is required here (not DFS) because we need the shortest path, not just any path.

Key Terms​

TermDefinition
BFSBreadth-first search — explores nodes level by level, guaranteeing shortest path in unweighted graphs.
8-directional adjacencyNeighbors include the 4 orthogonal and 4 diagonal cells around a point.
In-place visited markingReusing the grid itself (setting cleared cells to 1) instead of a separate visited set, saving space.
Level/path lengthThe BFS queue tracks the number of cells visited so far, which equals the path length by construction.
Early terminationReturning as soon as the destination cell is reached avoids exploring the rest of the queue unnecessarily.

FAQ​

Q: Can this be solved without extra space? A: Not entirely — even with in-place visited marking (mutating the input grid), the BFS queue itself requires O(n²) space in the worst case for a fully open grid.

Q: What if the grid is empty or 1x1? A: An empty grid isn't a valid input per constraints, but the n == 1 case is handled explicitly — if grid[0][0] == 0, the answer is 1 (already at destination).

Q: How would this change if only 4-directional movement were allowed? A: Just shrink the directions list to the 4 orthogonal moves; the BFS structure and shortest-path guarantee stay identical.

Q: What is the time complexity trade-off vs DFS? A: DFS can find a path in O(n²) but does not guarantee the shortest one without exploring all paths (exponential blowup); BFS guarantees shortest path in the same O(n²) by exploring level-by-level.

Q: Why mark a neighbor visited when enqueuing rather than when dequeuing? A: Marking at enqueue time prevents the same cell from being added to the queue multiple times by different in-progress paths, avoiding redundant work and duplicate expansion.

Quick Revision​

  • Goal: shortest 8-directionally-connected path of 0-cells from (0,0) to (n-1,n-1).
  • Immediately return -1 if start or end cell is blocked (value 1).
  • Special-case n == 1: answer is 1 if the single cell is open.
  • Use BFS (not DFS) because BFS guarantees shortest path in unweighted graphs.
  • Queue holds (row, col, path_length); start with length 1 for the origin cell.
  • Explore all 8 directions per cell; mark visited immediately by setting grid value to 1.
  • Return length + 1 the moment the destination cell is reached.
  • If the queue empties without reaching the destination, return -1.
  • Time: O(n²), Space: O(n²) for the queue in the worst case.