1091. Shortest Path in Binary Matrix

Problem¶

Given an \(n \times n\) binary matrix, find the minimum number of cells in a path from the top-left to the bottom-right. You may move in any of 8 directions and may visit only cells containing 0; return -1 if no path exists.

[[0, 1],
 [1, 0]] -> 2  # (0, 0) -> (1, 1)

Key trick¶

Use BFS because each move has equal cost; the first time BFS reaches the destination gives the shortest path.

Trap¶

Path length counts cells, so the initial distance is 1.
Diagonal moves are allowed.
Mark cells visited when enqueuing them, not when dequeuing.
Either endpoint may be blocked.
In-place visitation mutates the input matrix.

Why is it interesting?¶

It models a matrix as an unweighted graph and tests whether you recognize BFS as a shortest-path algorithm.

Python solution¶

from collections import deque


class Solution:
    def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n = len(grid)

        if grid[0][0] or grid[n - 1][n - 1]:
            return -1

        q = deque([(0, 0, 1)]) # (row, col, path length)
        grid[0][0] = 1 # mark as visited

        while q:
            r, c, length = q.popleft()

            if (r, c) == (n - 1, n - 1):
                return length

            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if dr == 0 and dc == 0:
                        continue

                    nr, nc = r + dr, c + dc

                    if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                        grid[nr][nc] = 1
                        q.append((nr, nc, length + 1))

        return -1

Time complexity: \(O(n^2)\).

Space complexity: \(O(n^2)\).

Comment on my solution¶

Your solution is correct, idiomatic, and has optimal complexity. It correctly marks cells when enqueuing and starts the path length at 1.

The only notable behavior is that it mutates grid. Checking the destination before BFS is optional but makes the blocked-endpoint case explicit.

from collections import deque

# Ideas:
# - BFS starting at (0,0) with in-place marking turning 0 into 1
#   - first to reach (-1,-1) cell gives shortest path
# WORKS
class Solution:
    def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1:
            return -1

        q = deque([(0,0,1)]) # (row, col, path length)
        grid[0][0] = 1 # mark as visited

        while q:
            r, c, length = q.popleft()
            if (r, c) == (n - 1, n - 1):
                return length
            for dr in (-1,0,1):
                for dc in (-1,0,1):
                    if (dr, dc) == (0, 0):
                        continue
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < n) and (0 <= nc < n) and grid[nr][nc] == 0:
                        grid[nr][nc] = 1
                        q.append((nr, nc, length + 1))
        return -1