1091. Shortest Path in Binary Matrix - Explanation

Problem Link

Description

You are 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 (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:

  • All the visited cells of the path are 0.

  • All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).

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

Example 1:

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

Output: 3

Example 2:

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

Output: -1

Constraints:

  • 1 <= grid.length == grid[i].length <= 100
  • grid[i][j] is 0 or 1.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



Intuition

We need to find the shortest path from the top-left corner to the bottom-right corner in a binary matrix, where we can only travel through cells containing 0. Since we want the shortest path and each step has equal weight, BFS is the natural choice. BFS explores cells level by level, guaranteeing that the first time we reach the destination, we have found the shortest path. We can move in all 8 directions (horizontal, vertical, and diagonal), so we check all 8 neighbors at each step.

Algorithm

  1. If the start cell (0, 0) or end cell (N-1, N-1) is blocked (contains 1), return -1.
  2. Initialize a queue with the starting position (0, 0, 1) where 1 represents the path length.
  3. Use a visited set or array to track cells we have already explored.
  4. While the queue is not empty:
    • Dequeue a cell (r, c, length).
    • If this is the destination (N-1, N-1), return length as the shortest path.
    • For each of the 8 directions, check if the neighbor is valid, unvisited, and contains 0.
    • If so, mark it as visited and enqueue it with length + 1.
  5. If the queue empties without reaching the destination, return -1 (no path exists).
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)])
        visit = set((0, 0))
        direct = [(0, 1), (1, 0), (0, -1), (-1, 0),
                  (1, 1), (-1, -1), (1, -1), (-1, 1)]

        while q:
            r, c, length = q.popleft()
            if r == N - 1 and c == N - 1:
                return length

            for dr, dc in direct:
                nr, nc = r + dr, c + dc
                if (0 <= nr < N and 0 <= nc < N and grid[nr][nc] == 0 and
                    (nr, nc) not in visit):
                    q.append((nr, nc, length + 1))
                    visit.add((nr, nc))

        return -1

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n2)O(n ^ 2)

2. Breadth First Search (Overwriting the Input)

Intuition

This approach is similar to the standard BFS but optimizes space by using the input grid itself to store distances. Instead of maintaining a separate visited set, we overwrite each cell with its distance from the start. A cell value of 0 indicates unvisited, while any positive value represents the shortest distance to reach that cell. This eliminates the need for extra space while preserving the BFS guarantee of finding the shortest path.

Algorithm

  1. If the start or end cell is blocked, return -1.
  2. Initialize a queue with (0, 0) and set grid[0][0] = 1 (distance of 1).
  3. While the queue is not empty:
    • Dequeue a cell (r, c) and read its distance from grid[r][c].
    • If this is the destination, return the distance.
    • For each of the 8 neighbors, if the neighbor is in bounds and equals 0:
      • Set its value to dist + 1.
      • Enqueue the neighbor.
  4. Return -1 if the destination is unreachable.
class Solution:
    def shortestPathBinaryMatrix(self, grid: list[list[int]]) -> int:
        N = len(grid)
        direct = [0, 1, 0, -1, 0, 1, 1, -1, -1, 1]

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

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

        while q:
            r, c = q.popleft()
            dist = grid[r][c]

            if r == N - 1 and c == N - 1:
                return dist

            for d in range(9):
                nr, nc = r + direct[d], c + direct[d + 1]
                if 0 <= nr < N and 0 <= nc < N and grid[nr][nc] == 0:
                    grid[nr][nc] = dist + 1
                    q.append((nr, nc))

        return -1

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n2)O(n ^ 2)

Intuition

Standard BFS explores outward from the source in all directions. Bidirectional BFS runs two searches simultaneously: one from the start and one from the end. When the two search frontiers meet, we have found the shortest path. This reduces the search space significantly because instead of exploring a circle of radius d, we explore two circles of radius d/2. The total area explored is roughly half of what single-direction BFS would cover.

Algorithm

  1. Handle edge cases: if start or end is blocked, return -1. If the grid is 1x1, return 1.
  2. Initialize two queues: q1 starting from (0, 0) and q2 starting from (N-1, N-1).
  3. Mark the start cell with -1 and the end cell with -2 to distinguish the two frontiers.
  4. Alternate between expanding q1 and q2:
    • For each cell in the current queue, explore all 8 neighbors.
    • If a neighbor belongs to the other frontier (end or start), return the current path length.
    • If a neighbor is unvisited (0), mark it with the current frontier's marker and add it to the queue.
  5. Swap the queues and markers after each level, incrementing the path length.
  6. Return -1 if the frontiers never meet.
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
        if N == 1:
            return 1

        direct = [0, 1, 0, -1, 0, 1, 1, -1, -1, 1]
        q1 = deque([(0, 0)])
        q2 = deque([(N - 1, N - 1)])
        grid[0][0] = -1
        grid[N - 1][N - 1] = -2

        res = 2
        start, end = -1, -2
        while q1 and q2:
            for _ in range(len(q1)):
                r, c = q1.popleft()
                for d in range(9):
                    nr, nc = r + direct[d], c + direct[d + 1]
                    if 0 <= nr < N and 0 <= nc < N:
                        if grid[nr][nc] == end:
                            return res
                        if grid[nr][nc] == 0:
                            grid[nr][nc] = start
                            q1.append((nr, nc))

            q1, q2 = q2, q1
            start, end = end, start
            res += 1

        return -1

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(n2)O(n ^ 2)