01 Matrix
Flood outwards from every zero at once so each cell takes the distance of the first one to reach it.
Examples
The only 1 already touches a 0.
(2, 1) is two steps from the nearest 0.
Problem Understanding
Given a matrix of 0s and 1s, replace every cell with its distance to the nearest 0, where a step is one move up, down, left or right (LeetCode 542).
- Input:
[[0,0,0],[0,1,0],[1,1,1]]. Output:[[0,0,0],[0,1,0],[1,2,1]]. - A
0is its own nearest zero, so it stays 0. - LeetCode guarantees at least one
0, so every cell has an answer.
The obvious reading — for each 1, search for the closest 0 — is a BFS per cell, which is O((R × C)²) and too slow. Turning the question round is what makes it linear.
Algorithm Strategy
Search from the zeroes instead of towards them.
- Queue every zero. They are all at distance 0, so they all start in the queue together — multi-source BFS again.
- Mark the rest
-1. One value says "no zero has reached this cell yet", so the matrix being returned is also the visited set. Nothing extra is allocated. - Flood outwards. Dequeue a cell and look at its four neighbours. One that is still
-1is being reached for the first time, so its distance is this cell's plus one, and it joins the queue. - Nothing is revisited. A cell already holding a number was reached by an equally close or closer zero, so it is skipped.
Why the first zero to arrive is the nearest one. BFS dequeues cells in order of distance, so when a cell is reached for the first time no shorter route to any zero can exist — which is why a distance is written once and never improved.
Interactive Visualization
The opening scan is stepped through, because it is the whole trick: every zero joins the queue together and every one becomes -1. A cell shows exactly what the matrix holds at that moment — 0, -1, or the distance it was given — so the figure and the matrix being returned are the same object. Watch the frontier: it is always one distance, or two neighbouring ones.
Dry Run
Input: [[0,0,0],[0,1,0],[1,1,1]]
The scan queues the five zeroes — (0,0), (0,1), (0,2), (1,0) and (1,2) — and sets the four ones to -1.
| Dequeued | Its distance | What it fills | Queue after |
|---|---|---|---|
| (0, 0) | 0 | nothing — every neighbour is already a 0 | (0,1) (0,2) (1,0) (1,2) |
| (0, 1) | 0 | (1, 1) = 1 | (0,2) (1,0) (1,2) (1,1) |
| (0, 2) | 0 | nothing | (1,0) (1,2) (1,1) |
| (1, 0) | 0 | (2, 0) = 1 | (1,2) (1,1) (2,0) |
| (1, 2) | 0 | (2, 2) = 1 | (1,1) (2,0) (2,2) |
| (1, 1) | 1 | (2, 1) = 2 | (2,0) (2,2) (2,1) |
The three remaining cells fill nothing new, and the matrix is [[0,0,0],[0,1,0],[1,2,1]]. Notice (2, 1): it was reached from (1, 1) at distance 1, giving 2 — and the cells beside it, already settled at 1, were skipped rather than rewritten.
Edge Cases & Common Mistakes
Edge Cases:
- All zeroes: the queue starts full and nothing is ever filled in — the answer is the input.
- One zero: the flood spreads from that single source, which is the ordinary single-source BFS.
- A single cell:
[[0]]is[[0]], and LeetCode guarantees a grid cannot be all ones.
Common Mistakes:
- A BFS from every 1, which is the O((R × C)²) version that times out.
- Not marking cells as unreached. Without the
-1, a cell holding 1 cannot be told apart from a cell whose distance is 1, so cells are re-queued and the distances come out wrong. - Overwriting a distance that is already set. The first value written is already the smallest; comparing and rewriting is wasted work.
Solution Code
Queue every zero at once and let the distances flood outwards (LeetCode 542).
01 Matrix Code
1var updateMatrix = function(mat) {2 const rows = mat.length, cols = mat[0].length;3 const queue = [];4 for (let r = 0; r < rows; r++) {5 for (let c = 0; c < cols; c++) {6 if (mat[r][c] === 0) {7 queue.push([r, c]);8 } else {9 mat[r][c] = -1;10 }11 }12 }13 const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];14 let head = 0;15 while (head < queue.length) {16 const [r, c] = queue[head++];17 for (const [dr, dc] of directions) {18 const nr = r + dr, nc = c + dc;19 if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || mat[nr][nc] !== -1) {20 continue;21 }22 mat[nr][nc] = mat[r][c] + 1;23 queue.push([nr, nc]);24 }25 }26 return mat;27};