#1091

Medium

auto_awesomeArray plus Breadth-First Search

LeetCode Problem Workspace

Shortest Path in Binary Matrix

Find the shortest clear path in a binary matrix using BFS, carefully handling obstacles and diagonal movements for efficiency.

array breadth first search matrix

Problem Statement

You are given an n x n binary matrix grid where 0 represents an open cell and 1 represents a blocked cell. Your task is to determine the length of the shortest clear path from the top-left cell to the bottom-right cell, moving in 8 possible directions (horizontal, vertical, and diagonal). If no clear path exists, return -1.

A clear path consists of a sequence of cells starting at (0, 0) and ending at (n - 1, n - 1), where every visited cell is 0. The path length is the number of cells traversed along this path, including the starting and ending cells.

Examples

Example 1

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

Output: 2

Example details omitted.

Example 2

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

Output: 4

Example details omitted.

Example 3

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

Output: -1

Example details omitted.

Constraints

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

Solution Approach

Breadth-First Search Initialization

Start BFS from the top-left cell if it is 0. Use a queue to track current positions along with their path length. Mark cells as visited to prevent revisiting and ensure shortest path calculation.

Expand in All 8 Directions

For each cell dequeued, attempt to move in 8 directions: up, down, left, right, and the four diagonals. Only enqueue cells that are within bounds and unblocked. Increment path length at each expansion.

Terminate on Reaching Target

If the bottom-right cell is reached during BFS, return the current path length immediately. If the queue empties without reaching it, return -1 indicating no clear path exists.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) because each cell can be visited at most once in BFS. Space complexity is O(n^2) for the queue and visited tracking, which grows with matrix size.

What Interviewers Usually Probe

Focus on BFS rather than DFS to guarantee minimal path length.
Check early for blocked start or end cells to avoid unnecessary computation.
Consider all 8 movement directions and ensure proper bounds checking.

Common Pitfalls or Variants

Common pitfalls

Forgetting to count the starting cell in the path length.
Not handling diagonal movements correctly, leading to wrong path lengths.
Revisiting cells and overcounting path lengths, missing BFS shortest-path guarantee.

Follow-up variants

Compute the shortest path in a rectangular m x n binary matrix instead of square.
Allow only 4-directional movement to simplify BFS but change minimal path results.
Return all shortest paths rather than just the length, adding tracking of paths.

FAQ

What is the shortest path in a binary matrix?

It is the minimal number of cells traversed from the top-left to bottom-right moving through zeros only, including diagonals.

Can I move diagonally in this problem?

Yes, all 8 directions (horizontal, vertical, and diagonal) are allowed and must be considered in BFS.

What if the start or end cell is blocked?

Return -1 immediately because no clear path can exist if either cell is blocked.

Why use BFS instead of DFS here?

BFS guarantees the shortest path in unweighted grids, whereas DFS may explore longer paths first.

How does GhostInterview handle this Array plus BFS pattern?

It guides through proper queue management, cell visitation tracking, and correct expansion in all 8 directions for minimal path computation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        if grid[0][0]:
            return -1
        n = len(grid)
        grid[0][0] = 1
        q = deque([(0, 0)])
        ans = 1
        while q:
            for _ in range(len(q)):
                i, j = q.popleft()
                if i == j == n - 1:
                    return ans
                for x in range(i - 1, i + 2):
                    for y in range(j - 1, j + 2):
                        if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:
                            grid[x][y] = 1
                            q.append((x, y))
            ans += 1
        return -1

Continue Practicing

#1034 coloring a border #1020 number of enclaves #1162 as far from land as possible