Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumgrid-graph-bfs

01 Matrix

Problem (restated)

Given a binary matrix, return a matrix of the same size where each cell holds the distance to the nearest 0 (4-directional). Distance is the number of steps to an adjacent cell.

Intuition

Distance-to-nearest-zero is shortest path on an unweighted grid. Instead of BFS from every 1, start from all zeros at once (multi-source) so each cell is settled once.

Approaches

Multi-source BFS from all zeros

Tested only

Time O(m·n)Space O(m·n)

Idea. Enqueue every 0 with distance 0. Expand to 4-neighbors; when a neighbor would get a strictly smaller distance, update and enqueue. First visit is optimal on unweighted graphs.

Walkthrough. [[0,0,0],[0,1,0],[1,1,1]] → distances [[0,0,0],[0,1,0],[1,2,1]].

Trade-offs. Two-pass DP (top-left then bottom-right) also works in O(m·n) with less queue memory. Multi-source BFS is the pattern-aligned mental model.

Solution

export function updateMatrix(mat: number[][]): number[][] {
  const R = mat.length;
  const C = mat[0]!.length;
  const dist = Array.from({ length: R }, () => new Array<number>(C).fill(Infinity));
  const q: [number, number][] = [];
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (mat[r]![c] === 0) {
        dist[r]![c] = 0;
        q.push([r, c]);
      }
    }
  }
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  let head = 0;
  while (head < q.length) {
    const [r, c] = q[head++]!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
      if (dist[nr]![nc]! <= dist[r]![c]! + 1) continue;
      dist[nr]![nc] = dist[r]![c]! + 1;
      q.push([nr, nc]);
    }
  }
  return dist;
}

export function updateMatrix(mat: number[][]): number[][] {
  const R = mat.length;
  const C = mat[0]!.length;
  const dist = Array.from({ length: R }, () => new Array<number>(C).fill(Infinity));
  const q: [number, number][] = [];
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (mat[r]![c] === 0) {
        dist[r]![c] = 0;
        q.push([r, c]);
      }
    }
  }
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  let head = 0;
  while (head < q.length) {
    const [r, c] = q[head++]!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
      if (dist[nr]![nc]! <= dist[r]![c]! + 1) continue;
      dist[nr]![nc] = dist[r]![c]! + 1;
      q.push([nr, nc]);
    }
  }
  return dist;
}

Template connection

Same multi-source BFS as Rotting Oranges (994): seed all sources at distance 0, expand outward.

Reflection

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?