1091. Shortest Path in a Binary Matrix
Asked at Databricks, Anduril
Difficulty
Medium
Time
O(n^2)
Space
O(n^2)
Pattern
Array
Companies
2
Problem
You are given an n x n grid filled with 0s and 1s. A 0 is an open cell you may walk on, and a 1 is a blocked cell you must avoid.
Find the shortest clear path from the top-left cell (0, 0) to the bottom-right cell (n-1, n-1). A path is clear when every cell on it is 0. From one cell you may step to any of the 8 neighbors — the cells that share an edge or a corner with it. The length of a path is the number of cells it visits, counting both the start and the end cell.
Return the length of the shortest clear path. If no clear path exists, return -1. Note that if the start cell or the end cell is 1, no path can exist, so the answer is -1.
Walk from corner to corner on zeros
Constraints
- ●
n == grid.length - ●
n == grid[i].length - ●
1 <= n <= 100 - ●
grid[i][j] is 0 or 1
Examples
grid = [[0,1],[1,0]]2grid = [[0,0,0],[1,1,0],[1,1,0]]4grid = [[1,0,0],[1,1,0],[1,1,0]]-1Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks questions → |
| Anduril | Medium | View all Anduril questions → |
How to Think About It
Why BFS? In an unweighted grid, BFS explores all cells at distance 1 before distance 2, and so on. The first time you reach the bottom-right cell, you have the shortest path. DFS would explore one path to the end before backtracking, which doesn't guarantee shortest path.
Setup: use a queue, start at (0, 0) with path length 1. Mark (0, 0) as visited (set matrix[0][0] = 1). For each cell, explore all 8 neighbors. If a neighbor is within bounds, is 0 (open), and unvisited, enqueue it with path length + 1.
8-direction movement: use a directions array: [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]. This covers all adjacent cells including diagonals.
Early termination: as soon as you pop (n-1, n-1) from the queue, return the path length. BFS guarantees this is optimal. Time: O(n²) since each cell is visited at most once. Space: O(n²) for the queue and visited set.
Optimal Approach
BFS from (0, 0). Use a queue storing (row, col, distance). Start by enqueueing (0, 0, 1) and marking matrix[0][0] = 1.
While queue is not empty:
- Dequeue (r, c, dist).
- If r == n-1 and c == n-1, return dist.
- For each of the 8 neighbors (nr, nc):
- If in bounds, matrix[nr][nc] == 0: mark as visited, enqueue (nr, nc, dist + 1).
- If queue empties without reaching destination, return -1.
Walkthrough: matrix = [[0,1],[1,0]]. Start (0,0) dist=1. Neighbors of (0,0): (0,1)=1 skip, (1,0)=1 skip, (1,1)=0 enqueue (1,1,2). Pop (1,1,2). It's the destination. Return 2.
Time: O(n²). Space: O(n²).
BFS spreads out in rings
What Trips People Up in Real Interviews
Using DFS instead of BFS. DFS finds a path, not the shortest path. You must use BFS for unweighted shortest path problems. This is the single most important distinction.
Forgetting to mark cells as visited when enqueuing, not when dequeuing. If you mark on dequeue, other paths might enqueue the same cell before it's processed, leading to duplicate work and wrong results.
Off-by-one in path length. Start with length 1 (the starting cell). Each neighbor adds 1. If you start with length 0, your answer will be off by 1.
Not checking if the start or end cell is blocked. If matrix[0][0] = 1 or matrix[n-1][n-1] = 1, return -1 immediately. BFS would never reach the destination.
Using a hash set for visited instead of modifying the matrix. Modifying the matrix in-place is cleaner and saves O(n²) space. Just set matrix[i][j] = 1 when visited. Since the matrix is binary, 1 already means blocked, so it doubles as visited.
Solution Code
O(n^2) timefrom collections import deque
def shortestPathBinaryMatrix(grid):
n = len(grid)
if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
return -1
directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
queue = deque([(0, 0, 1)])
grid[0][0] = 1
while queue:
r, c, dist = queue.popleft()
if r == n - 1 and c == n - 1:
return dist
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
grid[nr][nc] = 1
queue.append((nr, nc, dist + 1))
return -1Frequently Asked Questions
What is the Shortest Path in a Binary Matrix problem?
Given an n x n binary matrix (0 = open, 1 = blocked), find the shortest path from top-left to bottom-right. You can move in 8 directions. BFS guarantees the shortest path in an unweighted grid, making this a straightforward application of the BFS pattern.
How do you solve Shortest Path in a Binary Matrix?
The optimal approach runs in O(n^2) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Shortest Path in a Binary Matrix?
Shortest Path in a Binary Matrix is asked at Databricks, Anduril. It is a medium difficulty problem.
What are common mistakes on Shortest Path in a Binary Matrix?
- Using DFS instead of BFS. DFS finds *a* path, not the *shortest* path. You must use BFS for unweighted shortest path problems. This is the single most important distinction.
- Forgetting to mark cells as visited when enqueuing, not when dequeuing. If you mark on dequeue, other paths might enqueue the same cell before it's processed, leading to duplicate work and wrong results.
- Off-by-one in path length. Start with length 1 (the starting cell). Each neighbor adds 1. If you start with length 0, your answer will be off by 1.
- Not checking if the start or end cell is blocked. If `matrix[0][0]` = 1 or `matrix[n-1][n-1]` = 1, return -1 immediately. BFS would never reach the destination.
- Using a `hash set` for visited instead of modifying the matrix. Modifying the matrix in-place is cleaner and saves `O(n²)` space. Just set `matrix[i][j]` = 1 when visited. Since the matrix is binary, 1 already means blocked, so it doubles as visited.