542. 01 Matrix

Given an m × n binary matrix, return a matrix where each cell holds the distance to the nearest 0. Adjacent cells are distance 1 apart.

Start a BFS from every 0 at once. The first time the wave reaches a cell, that distance is its shortest distance to a 0.

1function updateMatrix(mat: number[][]): number[][] {
2  const m = mat.length, n = mat[0].length, queue: number[][] = [];
3  const dist = mat.map((row, r) => row.map((v, c) => (v === 0 ? (queue.push([r, c]), 0) : Infinity)));
4  for (let h = 0; h < queue.length; h++) {
5    const [r, c] = queue[h];
6    for (const [x, y] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]])
7      if (x >= 0 && y >= 0 && x < m && y < n && dist[x][y] > dist[r][c] + 1) {
8        dist[x][y] = dist[r][c] + 1; queue.push([x, y]);
9      }
10  }
11  return dist;
12}

dist

0	∞	∞	∞
∞	∞	∞	∞
∞	∞	0	∞
∞	∞	∞	∞

queue (pending)

(0,0)

(2,2)

Every 0 is distance 0. Queue all 2 of them.

1 / 0

Space: play/pause · ←/→: step