1091. Shortest Path in Binary Matrix - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Description:
You are given an n x n binary matrix grid where:

0 represents a clear cell.
1 represents a blocked cell.

A clear path in the matrix is a path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1) such that all visited cells are 0. In addition, you can move in 8 directions (horizontal, vertical, and diagonal). The length of a path is the number of visited cells.

Return the length of the shortest clear path. If no such path exists, return -1.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 2
Explanation:
The path (0,0) -> (1,1) is clear and its length is 2.

Example 2:

Input:

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

Output: 4
Explanation:
One shortest clear path is (0,0) -> (0,1) -> (1,2) -> (2,2), which visits 4 cells.

Constraints:

1 ≤ grid.length = grid[0].length ≤ 100
grid[i][j] is either 0 or 1.

Intuition and Hints

Graph Traversal on a Grid:
Think of the matrix as a graph where each cell is a node. There is an edge between two nodes if they are adjacent in any of the 8 directions and both are clear (value 0).
Shortest Path:
Since all moves have equal "cost" (each move counts as 1 step), Breadth-First Search (BFS) is a natural choice because it finds the shortest path in an unweighted graph.
Movement Directions:
Remember that you can move diagonally. Define the 8 possible moves and check bounds carefully.
Edge Cases:
- If the starting cell (0, 0) or the destination cell (n-1, n-1) is blocked (value 1), no path exists.
- If the grid is a single cell (1x1) and it’s clear, the answer is 1.

Approaches

Approach 1: Breadth-First Search (BFS)

Explanation:

BFS is ideal for finding the shortest path in an unweighted grid:

Check Start/End:
If grid[0][0] or grid[n-1][n-1] is blocked, return -1.
Initialization:
- Start at (0,0) with an initial path length of 1.
- Use a queue to perform the BFS.
Explore Neighbors:
For each cell, explore all 8 adjacent cells (neighbors). If a neighbor is in bounds and clear (0), add it to the queue with an updated path length and mark it as visited.
Termination:
When you reach (n-1, n-1), return the current path length. If the queue empties without reaching the destination, return -1.

Python Code (BFS Approach):

Python3

. . . .

Java Code (BFS Approach):

Java

. . . .

Approach 2: A* Search (Heuristic-Based)

Explanation:

A* Search improves upon BFS by using a heuristic to prioritize promising paths. In this grid:

Heuristic:
Use the Chebyshev distance (i.e. max(n-1 - r, n-1 - c)) because diagonal moves are allowed.
Priority Queue:
Use a min-heap (priority queue) where each element stores:
- The current path cost.
- The estimated total cost (current cost + heuristic).
- The cell coordinates.
Algorithm:
- Start from (0, 0) with an initial cost.
- At each step, choose the cell with the lowest estimated total cost.
- When reaching (n-1, n-1), return the current path cost.
- Mark cells as visited when they’re added to the queue.

Note: In the worst-case scenario, A* behaves like BFS (O(n²)), but with a good heuristic, it can often explore fewer nodes.

Python Code (A Approach):*

Python3

. . . .

Java Code (A* Approach):

Java

. . . .

Complexity Analysis

BFS Approach:
- Time Complexity: O(n²) in the worst-case scenario, where n is the side length of the matrix.
- Space Complexity: O(n²) for the queue and for marking visited cells.
A* Approach:
- Time Complexity: In the worst case, O(n²) similar to BFS, but in practice, the heuristic can help prune the search space.
- Space Complexity: O(n²) in the worst case due to the priority queue.

Common Pitfalls & Edge Cases

Edge Cases:
- Blocked Start/End:
  If either grid[0][0] or grid[n-1][n-1] is 1, return -1.
- Single Cell:
  For a 1x1 grid with 0, the answer is 1.
Pitfalls:
- Boundary Checks:
  Always verify that neighbor indices are within bounds.
- Marking Visits:
  Ensure that visited cells are marked immediately to prevent re-processing.
- Mutable Grid:
  If multiple approaches are run on the same grid, remember that the grid is modified during the search.