01 Matrix
Problem
m × n binary matrix mat containing at least
one 0. For every cell, compute the distance (number of up/down/left/right steps)
to the closest 0, and return these distances as a matrix of the same
shape.[[0,0,0],[0,1,0],[0,0,0]]Output[[0,0,0],[0,1,0],[0,0,0]][[0,0,0],[0,1,0],[1,1,1]]Output[[0,0,0],[0,1,0],[1,2,1]]1 ≤ m·n ≤ 104 · mat[i][j] ∈ {0, 1} · at least one 0
Try it yourself
class Solution {
public int[][] updateMatrix(int[][] mat) {
}
}
Instinct Minimum moves, fewest steps or shortest transformation where every step costs the same: spread outward level by level with a queue.
Memory hack Ripples in a pond: every ring is one step farther, so the first ring that touches the target is the answer.
Open the Graph BFS guide →Approaches
Brute ForceCheck Every Zero (Manhattan Distance)
O((m·n)2)Space O(1) extraThere are no walls, so the step distance between two cells is simply their
Manhattan distance |r1-r2| + |c1-c2|. For every 1,
scan all cells and keep the minimum distance to a 0.
public int[][] updateMatrix(int[][] mat) { int m = mat.length, n = mat[0].length; int[][] dist = new int[m][n]; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (mat[r][c] == 0) continue; int best = Integer.MAX_VALUE; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (mat[i][j] == 0) best = Math.min(best, Math.abs(i-r) + Math.abs(j-c)); dist[r][c] = best; } } return dist; }
Tiny code, but every 1 rescans the whole matrix — TLE on 104 cells.
BetterMulti-Source BFS from All Zeros
O(m·n)Space O(m·n)Seed the queue with every 0 (distance 0) and mark all
1s as -1 (unvisited). BFS expands in rings, so when a
cell is first reached its distance = parent + 1 is already minimal. Each cell is
enqueued once.
public int[][] updateMatrix(int[][] mat) { int m = mat.length, n = mat[0].length; int[][] dist = new int[m][n]; Queue<int[]> queue = new LinkedList<>(); for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (mat[r][c] == 0) queue.offer(new int[]{r, c}); else dist[r][c] = -1; // not reached yet } } int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; while (!queue.isEmpty()) { int[] cur = queue.poll(); for (int[] d : dirs) { int nr = cur[0] + d[0], nc = cur[1] + d[1]; if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] == -1) { dist[nr][nc] = dist[cur[0]][cur[1]] + 1; queue.offer(new int[]{nr, nc}); } } } return dist; }
Linear time, but needs a queue that can hold the whole matrix.
OptimalTwo-Pass Dynamic Programming
O(m·n)Space O(1) extraWith no obstacles, a shortest path to the nearest zero moves monotonically. Pass 1 (top-left → bottom-right) takes the best of the up/left neighbours; pass 2 (bottom-right → top-left) refines with down/right. Together they cover all four quadrants.
public int[][] updateMatrix(int[][] mat) { int m = mat.length, n = mat[0].length, INF = m + n; int[][] dist = new int[m][n]; for (int r = 0; r < m; r++) { for (int c = 0; c < n; c++) { if (mat[r][c] == 0) continue; dist[r][c] = INF; if (r > 0) dist[r][c] = Math.min(dist[r][c], dist[r - 1][c] + 1); if (c > 0) dist[r][c] = Math.min(dist[r][c], dist[r][c - 1] + 1); } } for (int r = m - 1; r >= 0; r--) { for (int c = n - 1; c >= 0; c--) { if (r < m - 1) dist[r][c] = Math.min(dist[r][c], dist[r + 1][c] + 1); if (c < n - 1) dist[r][c] = Math.min(dist[r][c], dist[r][c + 1] + 1); } } return dist; }
Same O(m·n) time, no queue — only the output matrix is allocated.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Check Every Zero (Manhattan Distance) | O((m·n)2) | O(1) extra |
| Better | Multi-Source BFS from All Zeros | O(m·n) | O(m·n) |
| Optimal | Two-Pass Dynamic Programming | O(m·n) | O(1) extra |
- Searching from each 1 — O((mn)2); seed all the 0s instead.
- Marking visited on poll, not on enqueue — duplicate entries.
- Only one DP sweep — misses zeros below/right of a cell.
- Name the trick: reverse the search, start from every 0.
- BFS optimality: rings expand in non-decreasing distance.
- Offer the two-sweep DP when asked to drop the queue.