LeetCode 1091 - Shortest Path in Binary Matrix

The problem asks us to find the shortest path from the top-left corner (0, 0) to the bottom-right corner (n-1, n-1) of a given n x n binary matrix grid. A cell with a value of 0 is passable, while a cell with a value of 1 is blocked.

leetcodemediumarraybreadth-first-searchmatrix

LeetCode Problem 1091

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem asks us to find the shortest path from the top-left corner (0, 0) to the bottom-right corner (n-1, n-1) of a given n x n binary matrix grid. A cell with a value of 0 is passable, while a cell with a value of 1 is blocked. The path can move in any of the eight directions: up, down, left, right, and the four diagonals. The length of the path is the total number of cells visited, including both the start and end cells. If no path exists, we must return -1.

The input grid represents the terrain of the matrix, and the output is the integer length of the shortest path. Constraints tell us that 1 <= n <= 100, which means a matrix can have up to 10,000 cells, so a brute-force search that explores every path recursively would be too slow. Each cell can only be 0 or 1, simplifying the check for traversable paths.

Important edge cases include situations where either the start (0, 0) or end (n-1, n-1) cell is blocked, which immediately means no path exists. Another edge case is a matrix of size 1 x 1, which is trivially a path of length 1 if the only cell is 0.

Approaches

The brute-force approach would involve recursively exploring every possible path from (0, 0) to (n-1, n-1), backtracking whenever a cell is blocked or already visited. This guarantees correctness but is too slow, because the number of possible paths grows exponentially with n. The time complexity would be O(2^(n^2)), which is infeasible for n = 100.

The optimal solution leverages Breadth-First Search (BFS). BFS is ideal because it explores all paths in increasing order of length, ensuring that the first time we reach the bottom-right corner, it is along the shortest possible path. We maintain a queue to store cells to visit and mark cells as visited by updating the grid or using a separate visited matrix. BFS guarantees that we do not revisit cells unnecessarily.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^(n^2)) O(n^2) Recursively explore all paths, too slow for n=100
Optimal (BFS) O(n^2) O(n^2) Level-order traversal finds shortest path efficiently

Algorithm Walkthrough

  1. Check if the start (0, 0) or end (n-1, n-1) is blocked. If either is 1, return -1.
  2. Initialize a queue for BFS and add the starting cell (0, 0) with an initial path length of 1.
  3. Create a list of 8 directions representing all possible moves from a cell: up, down, left, right, and the four diagonals.
  4. While the queue is not empty, pop the front element (r, c, path_length).
  5. If (r, c) is the bottom-right corner, return path_length.
  6. For each of the 8 directions, calculate the neighbor cell (nr, nc). Check if it is within bounds and passable (value 0).
  7. Mark the neighbor as visited (e.g., set grid[nr][nc] = 1) and add (nr, nc, path_length + 1) to the queue.
  8. If the queue is exhausted without reaching the target, return -1.

Why it works: BFS explores all cells in increasing order of path length. By marking cells visited, we avoid cycles and redundant work. When we reach the destination, the path length is guaranteed to be minimal.

Python Solution

from collections import deque
from typing import List

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] != 0 or grid[n-1][n-1] != 0:
            return -1
        
        directions = [(-1, -1), (-1, 0), (-1, 1),
                      (0, -1),          (0, 1),
                      (1, -1), (1, 0),  (1, 1)]
        
        queue = deque([(0, 0, 1)])  # row, col, path_length
        grid[0][0] = 1  # mark visited
        
        while queue:
            r, c, length = queue.popleft()
            if r == n - 1 and c == n - 1:
                return length
            for dr, dc in directions:
                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, length + 1))
        
        return -1

The code first checks for blocked start or end cells. The BFS queue stores each cell with the current path length. Each step, neighbors are calculated and added to the queue if valid, and cells are marked visited to prevent revisiting. The first time the target is reached, the shortest path length is returned.

Go Solution

package main

func shortestPathBinaryMatrix(grid [][]int) int {
    n := len(grid)
    if grid[0][0] != 0 || grid[n-1][n-1] != 0 {
        return -1
    }

    directions := [8][2]int{
        {-1, -1}, {-1, 0}, {-1, 1},
        {0, -1},          {0, 1},
        {1, -1}, {1, 0}, {1, 1},
    }

    type cell struct {
        r, c, length int
    }

    queue := []cell{{0, 0, 1}}
    grid[0][0] = 1

    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        if curr.r == n-1 && curr.c == n-1 {
            return curr.length
        }
        for _, d := range directions {
            nr, nc := curr.r+d[0], curr.c+d[1]
            if nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0 {
                grid[nr][nc] = 1
                queue = append(queue, cell{nr, nc, curr.length + 1})
            }
        }
    }

    return -1
}

The Go implementation mirrors the Python solution. We define a cell struct to store row, column, and path length. We use a slice as a queue, popping the first element and appending neighbors. Cells are marked visited by setting them to 1.

Worked Examples

Example 1: grid = [[0,1],[1,0]]

Step Queue Current Cell Action
1 [(0,0,1)] (0,0) Add (1,1,2)
2 [(1,1,2)] (1,1) Reached target, return 2

Example 2: grid = [[0,0,0],[1,1,0],[1,1,0]]

Step Queue Current Cell Action
1 [(0,0,1)] (0,0) Add (0,1,2),(1,0 blocked),(1,1 blocked),(1,1 diagonal blocked)
2 [(0,1,2),(0,2,2)] (0,1) Add (1,2,3)
3 [(0,2,2),(1,2,3)] (0,2) Add (1,2 already queued),(1,3 out of bounds),(1,1 blocked)
4 [(1,2,3)] (1,2) Add (2,2,4)
5 [(2,2,4)] (2,2) Reached target, return 4

Example 3: grid = [[1,0,0],[1,1,0],[1,1,0]]

Step Queue Current Cell Action
1 [] - Start blocked, return -1

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Each cell is visited at most once, 8 neighbors checked each time
Space O(n^2) BFS queue can grow up to the size of the grid

Since BFS explores each cell only once, the algorithm is efficient for the maximum grid size 100 x 100.

Test Cases

# provided examples
assert Solution().shortestPathBinaryMatrix([[0,1],[1,0]]) == 2  # shortest path exists
assert Solution().shortestPathBinaryMatrix([[0,0,0],[1,1,0],[1,