Problem Description

You are given an n x n binary matrix grid where each cell contains either a 0 or a 1. Your task is to find the length of the shortest clear path from the top-left corner (0, 0) to the bottom-right corner (n-1, n-1).

A clear path must satisfy these conditions:

• Every cell visited along the path must contain a 0
• You can move in 8 directions from any cell - horizontally, vertically, and diagonally (to any of the 8 neighboring cells that share an edge or corner)
• The path starts at cell (0, 0) and ends at cell (n-1, n-1)

The length of a clear path is counted as the total number of cells visited along the path, including both the starting and ending cells.

If no valid clear path exists from the top-left to the bottom-right corner, return -1.

For example:

• If the starting cell (0, 0) contains a 1, no path is possible, so return -1
• If the ending cell (n-1, n-1) contains a 1, no path can reach it, so return -1
• The minimum possible path length is 1 (when n = 1 and the single cell contains 0)

The solution uses BFS (Breadth-First Search) to explore all possible paths level by level, ensuring the first path found to the destination is the shortest. It marks visited cells by changing their value from 0 to 1 to avoid revisiting them, and tracks the path length by counting the number of levels traversed in the BFS.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The binary matrix can be viewed as a graph where each cell is a node, and edges connect to the 8 adjacent cells (if they contain 0s).

Is it a tree?

• No: The graph is not a tree because there can be multiple paths between cells, and cycles are possible.

Is the problem related to directed acyclic graphs?

• No: The graph is undirected (you can move in any of the 8 directions from any cell), and it may contain cycles.

Is the problem related to shortest paths?

• Yes: We need to find the shortest clear path from the top-left corner to the bottom-right corner.

Is the graph Weighted?

• No: All moves between adjacent cells have the same cost (each step counts as 1 in the path length). The graph is unweighted.

BFS

• Yes: Since we need to find the shortest path in an unweighted graph, BFS is the optimal choice.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for finding the shortest path in this unweighted grid graph. BFS explores cells level by level, guaranteeing that the first time we reach the destination, we've found the shortest path.

Intuition

When we need to find the shortest path in a grid, we should think about how to explore all possible paths systematically. The key insight is that this problem is essentially a graph traversal problem where each cell with value 0 is a node, and we can move to any of its 8 neighboring cells.

Why BFS over DFS? Consider how these algorithms explore paths:

• DFS would go deep into one path completely before backtracking to try another path. It might find a valid path, but not necessarily the shortest one.
• BFS explores all paths level by level - first all cells at distance 1, then all cells at distance 2, and so on. This guarantees that the first time we reach the destination, we've found the shortest path.

Think of it like ripples in water - when you drop a stone at the starting point (0, 0), the ripples spread outward uniformly in all directions. The first ripple that reaches the destination (n-1, n-1) represents the shortest path.

The 8-directional movement means we treat diagonal moves the same as horizontal/vertical moves (each counts as 1 step). This is different from some maze problems where diagonal moves might cost more or aren't allowed at all.

To avoid revisiting cells and getting stuck in cycles, we need to mark cells as visited. A clever optimization is to reuse the input grid itself - we can mark visited cells by changing their value from 0 to 1. This serves two purposes:

1. Prevents revisiting the same cell (avoiding infinite loops)
2. Ensures we only explore valid paths (cells with value 0)

The BFS implementation uses a queue to process cells level by level. We track the current path length by counting how many levels we've traversed. Each level represents one additional step in our path, so when we finally reach the destination, the level count gives us the shortest path length.

Learn more about Breadth-First Search patterns.

Solution Approach

Let's walk through the BFS implementation step by step:

Initial Setup and Edge Case Handling: First, we check if the starting cell grid[0][0] contains a 1. If it does, there's no valid path, so we immediately return -1.

Initialization:

• Mark the starting cell as visited by setting grid[0][0] = 1
• Initialize a queue (deque) with the starting position (0, 0)
• Set ans = 1 to track the path length (starting cell counts as 1)

BFS Level-by-Level Traversal: The main BFS loop continues while the queue is not empty:

1. Process Current Level: For each level, we process all cells currently in the queue using for _ in range(len(q)). This ensures we handle all cells at the current distance before moving to the next distance level.

2. Check for Destination: For each cell (i, j) popped from the queue, we check if we've reached the bottom-right corner with if i == j == n - 1. If yes, return the current path length ans.

3. Explore 8 Neighbors: For the current cell, we explore all 8 adjacent cells using nested loops:

   for x in range(i - 1, i + 2):
       for y in range(j - 1, j + 2):

   This generates all combinations where x is in [i-1, i, i+1] and y is in [j-1, j, j+1], covering all 8 directions including diagonals.

4. Validate and Mark Neighbors: For each neighbor (x, y):

   • Check if it's within bounds: 0 <= x < n and 0 <= y < n
   • Check if it's unvisited and valid: grid[x][y] == 0
   • If both conditions are met:
     • Mark as visited: grid[x][y] = 1
     • Add to queue for next level: q.append((x, y))

5. Increment Path Length: After processing all cells at the current level, increment ans += 1 to account for moving one step further.

Return Value: If the queue becomes empty without reaching the destination, no valid path exists, so return -1.

Time Complexity: O(n²) - In the worst case, we visit every cell in the n x n grid once.

Space Complexity: O(n²) - The queue can contain at most O(n²) cells in the worst case when many cells are reachable at the same distance level.

Example Walkthrough

Let's walk through a small example to illustrate the BFS solution approach.

Consider this 3×3 grid:

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

Initial Setup:

• Check grid[0][0] = 0 ✓ (valid starting point)
• Mark start as visited: grid[0][0] = 1
• Initialize queue with (0,0) and ans = 1

Level 1 (ans = 1):

• Process (0,0) from queue
• Check if (0,0) is destination (2,2)? No
• Explore 8 neighbors of (0,0):
  • (-1,-1): out of bounds, skip
  • (-1,0): out of bounds, skip
  • (-1,1): out of bounds, skip
  • (0,-1): out of bounds, skip
  • (0,0): already visited (value = 1), skip
  • (0,1): valid and unvisited (value = 0), mark as 1, add to queue
  • (1,-1): out of bounds, skip
  • (1,0): value = 1, skip
  • (1,1): value = 1, skip
• Queue now contains: [(0,1)]
• Grid state after Level 1:

[[1,1,0],
 [1,1,0],
 [1,1,0]]

• Increment ans = 2

Level 2 (ans = 2):

• Process (0,1) from queue
• Check if (0,1) is destination (2,2)? No
• Explore 8 neighbors of (0,1):
  • Only (0,2) is valid (unvisited with value 0)
  • Mark grid[0][2] = 1 and add to queue
• Queue now contains: [(0,2)]
• Grid state after Level 2:

[[1,1,1],
 [1,1,0],
 [1,1,0]]

• Increment ans = 3

Level 3 (ans = 3):

• Process (0,2) from queue
• Check if (0,2) is destination (2,2)? No
• Explore 8 neighbors of (0,2):
  • Only (1,2) is valid (unvisited with value 0)
  • Mark grid[1,2] = 1 and add to queue
• Queue now contains: [(1,2)]
• Grid state after Level 3:

[[1,1,1],
 [1,1,1],
 [1,1,0]]

• Increment ans = 4

Level 4 (ans = 4):

• Process (1,2) from queue
• Check if (1,2) is destination (2,2)? No
• Explore 8 neighbors of (1,2):
  • Only (2,2) is valid (unvisited with value 0)
  • Mark grid[2][2] = 1 and add to queue
• Queue now contains: [(2,2)]
• Grid state after Level 4:

[[1,1,1],
 [1,1,1],
 [1,1,1]]

• Increment ans = 5

Level 5 (ans = 5):

• Process (2,2) from queue
• Check if (2,2) is destination (2,2)? Yes!
• Return ans = 5

The shortest path is: (0,0) → (0,1) → (0,2) → (1,2) → (2,2) with length 5.

Note how BFS guarantees this is the shortest path - we explored all cells reachable in 1 step, then 2 steps, and so on. The first time we reached the destination, we had found the optimal solution.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm uses BFS to traverse the grid. In the worst case, we visit each cell at most once. Since there are n × n cells in the grid, and for each cell we explore up to 8 neighbors (constant time), the total time complexity is O(n²).

Breaking down the operations:

• The outer while loop runs until the queue is empty
• Each cell (i, j) is added to the queue at most once (since we mark it as visited by setting grid[x][y] = 1)
• For each cell, we check at most 8 adjacent cells (3×3 grid centered at current cell minus the cell itself)
• Checking boundaries and adding to queue are O(1) operations

Therefore: O(n² × 8) = O(n²)

Space Complexity: O(n²)

The space complexity consists of:

• Queue space: In the worst case, the queue can contain O(n²) elements. This happens when we have a large connected component of zeros, and at some level of BFS, many cells are in the queue simultaneously. The maximum would be when cells form a diagonal pattern, potentially having O(n²) cells in the queue.
• We modify the input grid in-place for marking visited cells, so no additional space is needed for tracking visited cells.
• Other variables (ans, i, j, x, y) use O(1) space.

Therefore, the overall space complexity is O(n²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Modifying the Input Grid Without Restoration

The Problem: The solution modifies the input grid directly by marking visited cells with 1. This is a destructive operation that permanently changes the input data. If the caller needs to use the grid again after calling this function, they'll find it has been modified, which can lead to unexpected bugs.

Example Scenario:

grid = [[0,0,0],[1,1,0],[1,1,0]]
solution = Solution()
result1 = solution.shortestPathBinaryMatrix(grid)  # Returns 4
result2 = solution.shortestPathBinaryMatrix(grid)  # Returns -1 (grid is now all 1s!)

Solution: Create a separate visited tracking structure instead of modifying the input:

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
    if grid[0][0] == 1:
        return -1
  
    n = len(grid)
    visited = set()
    visited.add((0, 0))
  
    queue = deque([(0, 0)])
    path_length = 1
  
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            row, col = queue.popleft()
          
            if row == n - 1 and col == n - 1:
                return path_length
          
            for next_row in range(row - 1, row + 2):
                for next_col in range(col - 1, col + 2):
                    if (0 <= next_row < n and 
                        0 <= next_col < n and 
                        grid[next_row][next_col] == 0 and
                        (next_row, next_col) not in visited):
                      
                        visited.add((next_row, next_col))
                        queue.append((next_row, next_col))
      
        path_length += 1
  
    return -1

2. Not Checking if the Destination Cell is Blocked

The Problem: While the code checks if the starting cell is blocked, it doesn't explicitly check if the destination cell grid[n-1][n-1] is blocked before starting the BFS. This can lead to unnecessary computation when the destination is unreachable.

Solution: Add an early check for both start and end cells:

def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
    n = len(grid)
  
    # Check if start or end is blocked
    if grid[0][0] == 1 or grid[n-1][n-1] == 1:
        return -1
  
    # Handle single cell grid
    if n == 1:
        return 1
  
    # Continue with BFS...

3. Inefficient Neighbor Generation Including Current Cell

The Problem: The nested loops for x in range(i - 1, i + 2): for y in range(j - 1, j + 2): generate 9 positions including the current cell (i, j). Since the current cell is already visited, checking it again is wasteful.

Solution: Skip the current cell explicitly:

for next_row in range(row - 1, row + 2):
    for next_col in range(col - 1, col + 2):
        # Skip the current cell
        if next_row == row and next_col == col:
            continue
          
        if (0 <= next_row < n and 
            0 <= next_col < n and 
            grid[next_row][next_col] == 0):
            # Process neighbor...

Or use a predefined directions array:

directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]

for dx, dy in directions:
    next_row, next_col = row + dx, col + dy
    if (0 <= next_row < n and 
        0 <= next_col < n and 
        grid[next_row][next_col] == 0):
        # Process neighbor...