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:
0.The length of a clear path is the number of visited cells of this path.
Example 1:
Input: grid = [[0,1],[1,0]] Output: 2
Example 2:
Input: grid = [[0,0,0],[1,1,0],[1,1,0]] Output: 4
Example 3:
Input: grid = [[1,0,0],[1,1,0],[1,1,0]] Output: -1
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j] is 0 or 1Problem Overview: Given an n x n binary grid, find the length of the shortest path from the top-left cell to the bottom-right cell. Cells with value 0 are open and 1 are blocked. Movement is allowed in 8 directions (horizontal, vertical, and diagonal). If no path exists, return -1.
Approach 1: Breadth-First Search (BFS) Traversal (Time: O(n²), Space: O(n²))
Treat the grid as an implicit graph where each cell is a node and edges connect the 8 neighboring cells. Start a Breadth-First Search from (0,0) if the cell is open. BFS explores the grid level by level, which naturally finds the shortest path in an unweighted graph. Use a queue to process cells and mark visited cells directly in the grid or with a visited matrix to avoid revisiting. For every cell removed from the queue, iterate through the 8 possible directions and enqueue valid neighbors with distance +1. Because each cell is processed at most once, the traversal runs in O(n²) time with O(n²) space for the queue and visited tracking.
This approach works well because all edges have equal cost. BFS guarantees the first time you reach the bottom-right cell is the shortest path length. The grid structure also keeps the implementation simple since neighbors can be generated using a fixed direction array.
Approach 2: A* Search Algorithm (Time: O(n² log n), Space: O(n²))
The A* algorithm improves practical performance by guiding the search toward the target using a heuristic. Instead of a simple queue, maintain a priority queue ordered by f(n) = g(n) + h(n), where g(n) is the distance from the start and h(n) is a heuristic estimate to the goal. For this problem, the Chebyshev distance works well because diagonal movement is allowed. Each step expands the node with the smallest estimated total distance. In dense grids or large search spaces, A* often explores fewer cells than BFS.
The implementation still iterates over the 8 neighbors for every expanded node and updates distances when a shorter path is found. While the worst-case complexity remains O(n² log n) due to heap operations, the heuristic significantly reduces unnecessary exploration in many cases.
Recommended for interviews: BFS is the expected solution. Interviewers want to see that you recognize the grid as an unweighted graph and immediately apply BFS. Mentioning that the grid can be modeled as a graph and exploring neighbors in 8 directions demonstrates strong fundamentals in matrix traversal and array-based graph problems. A* is a strong follow-up discussion if optimization or pathfinding algorithms come up.
This approach involves using BFS to find the shortest path in an unweighted graph. BFS is well-suited for finding the shortest path because it explores all nodes at the present depth prior to moving on to nodes at the next depth level. By maintaining a queue that stores the current cell position and path length, we can efficiently determine the shortest path to the destination. Moreover, since the path can proceed in 8 possible directions, we must consider all potential moves from a given cell.
The function shortestPathBinaryMatrix uses BFS to explore each adjacent cell of the current cell in all 8 possible directions. The grid has been marked to indicate which cells have been visited, avoiding revisiting them and ensuring efficient path finding. If the bottom-right corner is reached, the function returns the path length; otherwise, it returns -1 if no path exists.
Time Complexity: O(n^2) because in the worst case, each cell of the n x n grid is visited once.
Space Complexity: O(n^2) due to the space needed to store the BFS queue.
A* is a popular pathfinding and graph traversal algorithm. It is capable of focusing specifically on the shortest path with the use of heuristics. In this case, the heuristic is the Chebyshev distance between the current cell and the bottom-right corner, which matches the grid's 8-directional movement. By combining the BFS strategy with a heuristic score, A* ensures an efficient pathfinding solution while avoiding unnecessary paths.
This solution deploys the A* algorithm to find the shortest clear path by including a heuristic function, ensuring efficient traversal through the grid by prioritizing paths closer to the end point.
Time Complexity: O(n^2 * log(n)) because each cell is processed once with priority queue operations.
Space Complexity: O(n^2) for the priority queue and grid storage.
| Approach | Complexity |
|---|---|
| Breadth-First Search Approach | Time Complexity: O(n^2) because in the worst case, each cell of the n x n grid is visited once. |
| A* Search Algorithm Approach | Time Complexity: O(n^2 * log(n)) because each cell is processed once with priority queue operations. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(n²) | O(n²) | Best general solution for shortest path in an unweighted grid |
| A* Search Algorithm | O(n² log n) | O(n²) | When heuristic guidance can reduce explored nodes in large grids |
Shortest Path in a Binary Matrix - Leetcode 1091 - Python • NeetCodeIO • 47,189 views views
Watch 9 more video solutions →Practice Shortest Path in Binary Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor