Shortest Path in a Binary Matrix
Asked at Databricks
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Databricks | Medium | View all Databricks 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.
Visual walkthrough for matrix [[0,0,0],[1,1,0],[0,0,0]]:
- Queue: [(0,0,1)]. Visited: {(0,0)}.
- Pop (0,0,1). Neighbors: (0,1)=0 -> enqueue (0,1,2). (1,0)=1 skip. (1,1)=1 skip.
- Queue: [(0,1,2)].
- Pop (0,1,2). Neighbors: (0,2)=0 -> enqueue (0,2,3). (1,2)=0 -> enqueue (1,2,3). Others blocked.
- Queue: [(0,2,3), (1,2,3)].
- Pop (0,2,3). Neighbors: (1,2) already visited. (1,1)=1 skip.
- Pop (1,2,3). Neighbors: (2,1)=0 -> enqueue (2,1,4). (2,2)=0 -> enqueue (2,2,4).
- Pop (2,1,4). Neighbors: (2,2) not yet processed.
- Pop (2,2,4). Reached bottom-right! Return 4.
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²).
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Shortest Path in a Binary Matrix?
Shortest Path in a Binary Matrix is asked at Databricks. 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.