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 1The key idea for solving #1091 Shortest Path in Binary Matrix is to find the minimum number of steps required to move from the top-left cell to the bottom-right cell in a grid containing 0s (open) and 1s (blocked). Since each move represents a single step and we must discover the shortest path, Breadth-First Search (BFS) is the most suitable strategy.
Start from cell (0,0) if it is not blocked and explore all possible directions. Unlike many grid problems, movement is allowed in 8 directions (horizontal, vertical, and diagonal). BFS processes cells level by level, ensuring the first time we reach the destination cell gives the shortest path length.
To avoid revisiting cells, mark visited positions or update the grid during traversal. A queue helps track the frontier of exploration. In the worst case, every cell may be visited once, making the algorithm efficient for typical matrix constraints.
The BFS traversal leads to a time complexity proportional to the number of cells in the grid, with additional space used for the queue and visited tracking.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search (BFS) on Grid | O(n²) | O(n²) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Do a breadth first search to find the shortest path.
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.
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.
1from collections import deque
2
3def shortestPathBinaryMatrix(grid):
4 n = len(grid)
5 if grid[0][0] != 0 or grid[n-1][n-1] != 0:
6 return -1
7 directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
8 queue = deque([(0, 0, 1)])
9 grid[0][0] = 1 # Visited
10 while queue:
11 x, y, length = queue.popleft()
12 if x == n-1 and y == n-1:
13 return length
14 for dx, dy in directions:
15 nx, ny = x + dx, y + dy
16 if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
17 queue.append((nx, ny, length + 1))
18 grid[nx][ny] = 1 # Mark as visited
19 return -1The 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.
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.
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.
1#include <vector>
2#include <queue>
3#include <cmath>
4using namespace std;
struct Node {
int cost, x, y;
bool operator>(const Node& other) const { return cost > other.cost; }
};
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
int n = grid.size();
if (grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
vector<pair<int, int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
priority_queue<Node, vector<Node>, greater<Node>> pq;
pq.push({1, 0, 0});
grid[0][0] = 1;
auto heuristic = [n](int x, int y) { return max(abs(x-(n-1)), abs(y-(n-1))); };
while (!pq.empty()) {
Node node = pq.top(); pq.pop();
int cost = node.cost, x = node.x, y = node.y;
if (x == n-1 && y == n-1) return cost;
for (auto [dx, dy] : directions) {
int nx = x + dx, ny = y + dy;
if (nx >= 0 && ny >= 0 && nx < n && ny < n && grid[nx][ny] == 0) {
grid[nx][ny] = 1;
pq.push({cost + 1 + heuristic(nx, ny), nx, ny});
}
}
}
return -1;
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, grid-based BFS problems like Shortest Path in Binary Matrix are common in technical interviews, including FAANG-style companies. They test understanding of graph traversal, matrix navigation, and shortest-path logic.
The optimal approach uses Breadth-First Search (BFS). Since BFS explores nodes level by level, it guarantees the shortest path in an unweighted grid while checking all 8 possible directions from each cell.
BFS is preferred because it naturally finds the shortest path in graphs where all edges have equal weight. DFS may explore longer paths first and does not guarantee the minimum distance without additional logic.
A queue is the main data structure used for BFS traversal. It helps process cells in increasing distance order, while a visited structure or in-place grid marking prevents revisiting the same cells.
This solution adapts the A* algorithm for C++ utilizing a priority queue to manage and update path costs based on the heuristic and cell exploration. Each potential node is evaluated and processed according to its least cost pathway towards the goal.