#542 01 Matrix
the problem
In plain words
A matrix holds 0s and 1s, with at least one 0. For every cell, find how many steps (up, down, left, right) it takes to reach the nearest 0. Return those distances as a matrix of the same size.
in mat = [[0,0,0],[0,1,0],[0,0,0]]
out [[0,0,0],[0,1,0],[0,0,0]]
The middle 1 has a 0 right next to it.
in mat = [[0,0,0],[0,1,0],[1,1,1]]
out [[0,0,0],[0,1,0],[1,2,1]]
The bottom-middle 1 is 2 steps from the nearest 0 — for example up, then up again.
- 1 ≤ m, n ≤ 10⁴
- 1 ≤ m · n ≤ 10⁴
- mat[i][j] is 0 or 1
- At least one 0
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMulti-source BFS
where this runsImage tools compute a distance transform — every pixel's distance to the nearest edge pixel — with the same two-sweep idea as the DP approach.
Searching from every 1 repeats work. Flip it: start one BFS from all the 0s at once. BFS reaches cells in order of distance, so the first time it touches a 1, that's its nearest 0.
solutions
From brute force to optimal
For each 1, run its own BFS outward until the first 0 is polled.
- For every cell with 1: BFS from it with a fresh distance grid.
- The first 0 polled gives that cell's answer.
Up to m·n searches, each of which can cover all m·n cells (think one 0 in a far corner).
A fresh distance grid and queue for each search.
class Solution { private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; /** For every 1, run its own BFS outwards until it bumps into a 0. */ public int[][] updateMatrix(int[][] mat) { int rows = mat.length, cols = mat[0].length; int[][] dist = new int[rows][cols]; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (mat[r][c] == 1) dist[r][c] = nearestZero(mat, r, c); return dist; } private int nearestZero(int[][] mat, int sr, int sc) { int rows = mat.length, cols = mat[0].length; int[][] steps = new int[rows][cols]; for (int[] row : steps) Arrays.fill(row, -1); Deque<int[]> queue = new ArrayDeque<>(); queue.offer(new int[] {sr, sc}); steps[sr][sc] = 0; while (!queue.isEmpty()) { int[] cell = queue.poll(); if (mat[cell[0]][cell[1]] == 0) return steps[cell[0]][cell[1]]; // first 0 polled is the nearest for (int[] d : DIRS) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || steps[nr][nc] != -1) continue; steps[nr][nc] = steps[cell[0]][cell[1]] + 1; queue.offer(new int[] {nr, nc}); } } return -1; // unreachable: the problem promises at least one 0 }}A shortest path to the nearest 0 comes in from above/left or from below/right. Sweep top-left → bottom-right taking up/left, then bottom-right → top-left taking down/right.
- dist = 0 for zeros, a big number for ones.
- Pass 1 (rows top→bottom, cols left→right): dist = min(dist, up + 1, left + 1).
- Pass 2 (rows bottom→top, cols right→left): dist = min(dist, down + 1, right + 1).
Two passes, O(1) work per cell.
Only the answer matrix, which you must return anyway.
class Solution { /** A shortest path to the nearest 0 arrives from above/left or from below/right: sweep both ways. */ public int[][] updateMatrix(int[][] mat) { int rows = mat.length, cols = mat[0].length; int far = rows + cols; // longer than any real distance int[][] dist = new int[rows][cols]; for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) { if (mat[r][c] == 0) continue; dist[r][c] = far; 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 = rows - 1; r >= 0; r--) for (int c = cols - 1; c >= 0; c--) { if (r + 1 < rows) dist[r][c] = Math.min(dist[r][c], dist[r + 1][c] + 1); if (c + 1 < cols) dist[r][c] = Math.min(dist[r][c], dist[r][c + 1] + 1); } return dist; }}Put every 0 in the queue first (distance 0). Mark the 1s as unknown (-1). BFS outward; each 1 gets its distance the first time it is reached.
- Enqueue every 0; set every 1 to -1.
- Poll a cell; for each neighbour still -1: dist = dist[cell] + 1, enqueue it.
- When the queue is empty, every cell has its answer.
Each cell is enqueued at most once and checks 4 neighbours.
The queue can hold many cells at once (all the 0s, to begin with).
class Solution { public int[][] updateMatrix(int[][] mat) { int rows = mat.length, cols = mat[0].length; int[][] dist = new int[rows][cols]; Deque<int[]> queue = new ArrayDeque<>(); for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) { if (mat[r][c] == 0) queue.offer(new int[] {r, c}); // every 0 is a source else dist[r][c] = -1; // not reached yet } int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; while (!queue.isEmpty()) { int[] cell = queue.poll(); for (int[] d : dirs) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || dist[nr][nc] != -1) continue; dist[nr][nc] = dist[cell[0]][cell[1]] + 1; queue.offer(new int[] {nr, nc}); } } return dist; }}Dry run
in the room
How to say it in the interview
talk track
- Say: "Many sources, one question — distance to the nearest. That's multi-source BFS, like Rotting Oranges."
- Explain why it's correct: BFS pops cells in order of distance from the set of 0s, so the first visit is the shortest.
- Offer the two-sweep DP as an alternative with O(1) extra space.
traps
- Starting BFS from each 1 — correct, but O((m·n)²).
- Using 0 as the "unvisited" mark for 1-cells: 0 is a real distance. Use -1 (or a visited grid).
- Doing only one DP sweep — a cell whose nearest 0 is below or to the right gets a wrong answer.
what they ask next
Follow-ups
Map of Highest Peak (LC 1765)?
LeetCode notes it's the same problem: water cells are the sources, and each land cell's height is its BFS distance from the nearest water.
What if some cells were walls you can't pass?
The DP sweeps break (paths may need to wind), but multi-source BFS still works — just skip wall cells. That's Walls and Gates.
before you submit
Edge cases to test
- Every cell is 0 → return all zeros.
- A single 0 in a far corner → distances grow up to m + n − 2.
- One row or one column — the answer is just distance along a line.
- Two 0s at both ends of a row of 1s → the middle gets the smaller of the two distances.
practise next
Similar problems
- #286Walls and GatesMediumin GraphsLeetCode Premium
- #994Rotting OrangesMediumin Graphs
- #1091Shortest Path in Binary MatrixMediumin Graphs