LeetCode 1091: Shortest Path in Binary Matrix

Problem Restatement

We are given an n x n binary matrix grid.

A clear path goes from (0, 0) to (n-1, n-1) using only cells with value 0, moving in 8 directions.

Return the length of the shortest clear path, or -1 if no such path exists.

The path length counts the number of cells visited.

The official constraints state that n == grid.length == grid[i].length, 1 <= n <= 100, and grid[i][j] is 0 or 1.

Input and Output

Function shape:

def shortestPathBinaryMatrix(grid: list[list[int]]) -> int:
    ...

Examples

Example 1:

grid = [[0,1],[1,0]]

Path: (0,0) → (1,1). Length 2.

Answer:

2

Example 2:

grid = [[0,0,0],[1,1,0],[1,1,0]]

One shortest path is (0,0) -> (0,1) -> (1,2) -> (2,2).

The length is 4 because the problem counts visited cells, including the start and the end.

Answer:

4

Key Insight

BFS guarantees the shortest path. Start from (0,0) and expand in all 8 directions. Return the distance when (n-1, n-1) is reached.

Algorithm

1. If grid[0][0] == 1 or grid[n-1][n-1] == 1, return -1.
2. BFS from (0, 0) with distance 1.
3. Expand to all 8 neighbors that are 0 and unvisited.
4. Return distance when (n-1, n-1) is reached, or -1 if BFS exhausts.

Edge Cases

• Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
• Return the failure value when the destination is unreachable.
• Check grid or graph boundaries before reading neighbors.

Complexity

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

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

        queue = deque([(0, 0, 1)])
        grid[0][0] = 1

        for r, c, dist in queue:
            if r == n - 1 and c == n - 1:
                return dist
            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
                        queue.append((nr, nc, dist + 1))

        return -1

Testing

def run_tests():
    s = Solution()

    assert s.shortestPathBinaryMatrix([[0,1],[1,0]]) == 2
    assert s.shortestPathBinaryMatrix([[0,0,0],[1,1,0],[1,1,0]]) == 4
    assert s.shortestPathBinaryMatrix([[1,0,0],[1,1,0],[1,1,0]]) == -1

    print("all tests passed")

run_tests()