The problem. You're given a grid of 0s and 1s with at least one 0. For every cell, find the distance to the nearest 0, counting steps up, down, left or right. Return a grid of those distances.
mat = [[0,0,0],
[0,1,0],
[1,1,1]] -> [[0,0,0],
[0,1,0],
[1,2,1]]
mat = [[1,1,1],
[1,0,1],
[1,1,1]] -> [[2,1,2],
[1,0,1],
[2,1,2]]The question is asked from every 1: where is my nearest 0? Answering it one cell at a time means one search per cell. Turn it around and ask from the 0s instead: start a BFS from all of them at once, exactly like the rotten oranges. Ring 1 of that search is every cell one step from some 0, ring 2 is every cell two steps away, and so on.
BFS reaches cells in order of distance, so the first time the search reaches a cell, it has come from that cell's nearest 0. Write the distance down then and never touch the cell again — the distance grid doubles as the visited marker.
For each 1, run a fresh BFS outwards until it meets a 0. The first 0 it meets is the nearest, because BFS goes ring by ring.
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function updateMatrix(mat) { const rows = mat.length, cols = mat[0].length; const dist = mat.map((row) => row.map(() => 0)); for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (mat[r][c] === 0) continue; // A fresh BFS from (r, c), stopped at the first 0 it meets. const seen = mat.map((row) => row.map(() => false)); seen[r][c] = true; const queue = [[r, c, 0]]; let head = 0; while (head < queue.length) { const [cr, cc, d] = queue[head++]; if (mat[cr][cc] === 0) { dist[r][c] = d; // the first 0 found is the nearest break; } for (const [dr, dc] of DIRS) { const nr = cr + dr, nc = cc + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !seen[nr][nc]) { seen[nr][nc] = true; queue.push([nr, nc, d + 1]); } } } } } return dist;}Time O((m · n)²), space O(m · n). Each of the m · n cells may run a search that visits most of the grid — a big block of 1s with a single 0 in one corner is the worst case. The searches also repeat each other's work over and over.
Put every 0 in the queue at distance 0 and mark every other cell not reached yet. Then run one ordinary BFS: each cell taken from the queue gives its unreached neighbours its own distance plus one.
One search spreads from every 0 at once; "?" is a cell not reached yet.
const DIRS = [[-1, 0], [1, 0], [0, -1], [0, 1]]; function updateMatrix(mat) { const rows = mat.length, cols = mat[0].length; const dist = mat.map((row) => row.map(() => -1)); // -1: not reached yet const queue = []; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (mat[r][c] === 0) { dist[r][c] = 0; // every 0 is a source, at distance 0 queue.push([r, c]); } } } let head = 0; while (head < queue.length) { const [r, c] = queue[head++]; for (const [dr, dc] of DIRS) { const nr = r + dr, nc = c + dc; if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] === -1) { dist[nr][nc] = dist[r][c] + 1; // first visit = nearest 0, one step further queue.push([nr, nc]); } } } return dist;}Time O(m · n), space O(m · n). Every cell enters the queue exactly once and checks 4 neighbours. The queue can hold up to m · n cells — all of them, if the grid is mostly 0s.
There are no walls, so the distance to a 0 is just rows apart + columns apart, and the steps can be taken in any order. That means a cell's answer can be built from its neighbours' answers: it's one more than the smallest of them.
Two sweeps are enough. The first goes top-left to bottom-right and takes the best from the cell above and the cell to the left, which it has already updated. The second goes bottom-right to top-left and also takes the cell below and to the right. Every nearest 0 can reach a cell by moving down or right first (carried by sweep 1) and then up or left (carried by sweep 2).
function updateMatrix(mat) { const rows = mat.length, cols = mat[0].length; const INF = rows + cols; // longer than any real distance const dist = mat.map((row) => row.map((v) => (v === 0 ? 0 : INF))); // Pass 1, top-left first: take the best from the cell above and the cell to the left. for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { 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); } } // Pass 2, bottom-right first: now also from the cell below and the cell to the right. for (let r = rows - 1; r >= 0; r--) { for (let c = cols - 1; c >= 0; c--) { if (r < rows - 1) dist[r][c] = Math.min(dist[r][c], dist[r + 1][c] + 1); if (c < cols - 1) dist[r][c] = Math.min(dist[r][c], dist[r][c + 1] + 1); } } return dist;}Time O(m · n), space O(1) extra. Two sweeps of the grid, and nothing stored besides the answer itself. This trick needs a grid with no walls — once some cells are blocked, steps can't be taken in any order and you're back to BFS.
In an interview, lead with the multi-source BFS: it's the pattern, and it still works when the grid has walls. Mention the two-pass version as the follow-up that saves the queue.
rows + cols - 2 steps away.