Graphs crash course ↗ · 185

542. 01 Matrix

For each cell, find the distance to the nearest 0. Running BFS from every 1 would be quadratic — instead flip it: seed one BFS with every 0 at once and let the wave wash outward, so the first time a cell is reached is its shortest distance.

● MediumMulti-source BFSDynamic ProgrammingTypeScript

PROBLEM What we're solving

Given an m × n binary matrix of 0s and 1s, replace each cell with its 4-directional distance to the nearest 0. Every 0 maps to 0.

Worked example. Input:

[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:

[[0,0,0],
 [0,1,0],
 [1,2,1]]

The center 1 at (1,1) is one step from three different 0s, so it becomes 1. The cell (2,1) is two steps from the nearest 0, so it becomes 2.

KEY IDEA Invert the search: BFS from the zeros, not the ones

Insight → the naive instinct is “for each 1, BFS until you hit a 0” — but that re-explores the grid for every cell. Flip it: enqueue every 0 at distance 0 and run a single multi-source BFS outward. Because BFS expands in concentric layers, the first time the wave touches a cell is necessarily along a shortest path — so the distance you assign on first contact is final.

RECIPE Seed all zeros, flood outward

0 · Seed. Scan the grid once. Push every 0-cell into the queue (its answer is already 0); set every 1-cell to Infinityto mark it unvisited. This collection of zeros is BFS “layer 0” — all sources at once.
1 · Flood.Pop a cell, look at its 4 neighbors. If a neighbor's current distance is greater than dist[cell] + 1, this BFS wave reaches it sooner: set dist[neighbor] = dist[cell] + 1 and enqueue it.
2 · Why first-touch wins. A plain queue (FIFO) processes cells in non-decreasing distance order, so the first assignment to any cell is the smallest possible — no need to ever revisit or relax again.
3 · Return. When the queue drains, every cell holds its true minimum distance. Return the dist grid.

Classic confusion → do not overwrite the input grid's 1s with the distance you compute and then use that same grid to decide “visited.” Mixing the input markers with the output distances corrupts the relaxation check. Keep a separate dist grid initialized to Infinity for the 1s; the dist[nbr] > dist[cur] + 1 test then doubles as the visited test for free.

COST Complexity & alternatives

BFS from every 1 independently

O((mn)²)

Each of mn cells re-scans up to mn others.

Multi-source BFS

O(mn)

Each cell enqueued and dequeued at most once.

The two-pass DP alternative

There is also an elegant dynamic-programming solution in O(mn) time and O(1) extra space (besides the output). Sweep top-left → bottom-right taking the min of the up and left neighbors + 1, then sweep bottom-right → top-left taking the min of the down and right neighbors + 1. Two passes suffice because any shortest path to a 0 is monotone in the four diagonal directions covered by the two sweeps. See the Approaches tab.

Pattern transfer →the “seed BFS with all sources” trick is the same one in Rotting Oranges (minutes until all rot), Walls and Gates (distance to nearest gate), and Nearest Exit from Entrance in Maze. Any prompt of the form “distance from anyof several sources” wants multi-source BFS.

RUN IT Multi-source BFS outward from every 0

mat (rows by ;)

step 0 / 15

STARTGrid is 3×3. Every 0 is its own nearest zero (distance 0); we seed the BFS queue with all of them at once and set every 1 to ∞ (unvisited).

1function updateMatrix(mat: number[][]): number[][] {
2▶  const rows = mat.length;
3▶  const cols = mat[0].length;
4▶  const dist: number[][] = mat.map((row) => row.slice());
5▶  const queue: [number, number][] = [];
6 
7  // Seed: every 0 is distance 0; every 1 starts at Infinity (unvisited)
8  for (let r = 0; r < rows; r++) {
9    for (let c = 0; c < cols; c++) {
10      if (mat[r][c] === 0) queue.push([r, c]);
11      else dist[r][c] = Infinity;
12    }
13  }
14 
15  const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
16  let head = 0;
17  while (head < queue.length) {
18    const [r, c] = queue[head++];
19    for (const [dr, dc] of dirs) {
20      const nr = r + dr, nc = c + dc;
21      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
22      if (dist[nr][nc] <= dist[r][c] + 1) continue;   // already shorter
23      dist[nr][nc] = dist[r][c] + 1;                  // first reach = shortest
24      queue.push([nr, nc]);
25    }
26  }
27 
28  return dist;
29}

State
head: 0
queue size: 0

source 0 / dequeued fromcurrently dequeuedjust assigned distancealready settled

slowfast

TYPESCRIPT The solution, annotated

updateMatrix.ts
function updateMatrix(mat: number[][]): number[][] {
  const rows = mat.length;
  const cols = mat[0].length;
  const dist: number[][] = mat.map((row) => row.slice());
  const queue: [number, number][] = [];

  // Seed: every 0 is distance 0; every 1 starts at Infinity (unvisited)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (mat[r][c] === 0) queue.push([r, c]);
      else dist[r][c] = Infinity;
    }
  }

  const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
  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) continue;
      if (dist[nr][nc] <= dist[r][c] + 1) continue;   // already shorter
      dist[nr][nc] = dist[r][c] + 1;                  // first reach = shortest
      queue.push([nr, nc]);
    }
  }

  return dist;
}

Reading it block by block

Lines 4–5 — separate dist grid. Copy the input into a fresh dist matrix so we never tangle the input markers with the distances we are writing. Zeros keep their value; ones will be overwritten.

Lines 8–14 — multi-source seed. One pass enqueues every 0-cell (its distance is already 0) and sets every 1-cell to Infinity. Seeding all zeros before the first pop is what makes this a single linear BFS instead of many.

Lines 17–18 — head pointer queue. head advances through the shared array; this is an O(1) dequeue and avoids the O(n) cost of Array.shift().

Lines 20–23 — relax neighbors. For each in-bounds neighbor, the test dist[nr][nc] <= dist[r][c] + 1 skips cells already reached as soon (or sooner). Otherwise we set dist[nr][nc] = dist[r][c] + 1 and enqueue it. Because BFS visits in non-decreasing distance order, this first assignment is the minimum.

Line 27 — done. When head catches up to queue.length, every reachable cell (all of them, since the grid is connected through non-walls) holds its shortest distance. Return dist.

Complexity → O(mn) time — each cell is enqueued and dequeued at most once, and each does O(1) work per its 4 neighbors. O(mn) space for the queue in the worst case (a grid that is all zeros seeds the entire queue up front). The separate dist grid is the output, so it is not counted as extra.

INTERVIEWFollow-ups they'll ask

"Can you do it without the extra dist grid?" The two-pass DP runs in O(mn) time and O(1) extra space by computing the answer in place (min of up/left, then down/right). Walk the interviewer through why two sweeps suffice.
"Why does first-touch give the shortest distance?" A FIFO queue dequeues cells in non-decreasing distance order, so the first time any cell is reached it is via a shortest path. This is the core BFS invariant.
"What if movement were 8-directional?" Expand dirs from 4 to 8 entries — the BFS structure is unchanged.
"What if cells had varying move costs?" BFS no longer suffices; switch to Dijkstra with a min-heap, seeding all zeros at distance 0.
"What if there are no zeros at all?" The queue starts empty and the loop never runs; every cell stays Infinity (LeetCode guarantees at least one 0, but state the edge case).

OPTIMAL Multi-source BFS

updateMatrix.ts
function updateMatrix(mat: number[][]): number[][] {
  const rows = mat.length;
  const cols = mat[0].length;
  const dist: number[][] = mat.map((row) => row.slice());
  const queue: [number, number][] = [];

  // Seed: every 0 is distance 0; every 1 starts at Infinity (unvisited)
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (mat[r][c] === 0) queue.push([r, c]);
      else dist[r][c] = Infinity;
    }
  }

  const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
  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) continue;
      if (dist[nr][nc] <= dist[r][c] + 1) continue;   // already shorter
      dist[nr][nc] = dist[r][c] + 1;                  // first reach = shortest
      queue.push([nr, nc]);
    }
  }

  return dist;
}

ALT 1 Two-pass dynamic programming

O(mn) time · O(1) extra space

The shortest path to a 0 either comes from above/left or from below/right. Two directional sweeps capture both, so no queue is needed and the answer is built in place.

approach-2.ts
function updateMatrix(mat: number[][]): number[][] {
  const rows = mat.length;
  const cols = mat[0].length;
  const INF = rows + cols;   // larger than any real distance
  const dist: number[][] = mat.map((row) =>
    row.map((v) => (v === 0 ? 0 : INF)),
  );

  // Pass 1: top-left -> bottom-right (look up and 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 -> top-left (look down and 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;
}

Note → Same O(mn) time as BFS but no queue — O(1) auxiliary space. The trick: a shortest 4-directional path to a 0 is monotone, so the up/left sweep handles paths coming from those directions and the down/right sweep handles the rest. Use INF = rows + cols (not real Infinity) so + 1 never overflows.

ALT 2 BFS from every 1 (brute force)

O((mn)²) time · O(mn) space

The direct reading of the problem: for each 1, BFS outward until you hit a 0. Correct but quadratic.

approach-3.ts
function updateMatrix(mat: number[][]): number[][] {
  const rows = mat.length;
  const cols = mat[0].length;
  const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
  const res: number[][] = mat.map((row) => row.slice());

  for (let sr = 0; sr < rows; sr++) {
    for (let sc = 0; sc < cols; sc++) {
      if (mat[sr][sc] === 0) continue;
      // BFS from this single 1 to the nearest 0
      const seen = new Set<string>([`${sr},${sc}`]);
      let queue: [number, number, number][] = [[sr, sc, 0]];
      let head = 0;
      while (head < queue.length) {
        const [r, c, d] = queue[head++];
        if (mat[r][c] === 0) { res[sr][sc] = d; break; }
        for (const [dr, dc] of dirs) {
          const nr = r + dr, nc = c + dc;
          if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
          const key = `${nr},${nc}`;
          if (seen.has(key)) continue;
          seen.add(key);
          queue.push([nr, nc, d + 1]);
        }
      }
    }
  }

  return res;
}

Note → Each of the up to mn ones can scan up to mn cells → O((mn)²). This is the approach the multi-source BFS exists to avoid: invert it and run a single BFS seeded with all the zeros.

MNEMONIC The one-liner

"Pour from every zero at once; the first drop to reach a cell is its answer."

TRIGGERS When you see _ → reach for _

distance to nearest target from EVERY cell	multi-source BFS from all targets
"nearest 0 / gate / exit" on a grid	seed queue with all sources at distance 0
avoid (mn)² of per-cell BFS	one BFS seeded with all sources
O(1) extra space wanted	two-pass DP: up/left then down/right

SKELETON The reusable shape

skeleton.ts
const dist = mat.map((row) => row.slice());
const queue: [number, number][] = [];
for (let r = 0; r < rows; r++)
  for (let c = 0; c < cols; c++) {
    if (mat[r][c] === 0) queue.push([r, c]);
    else dist[r][c] = Infinity;
  }
let head = 0;
while (head < queue.length) {
  const [r, c] = queue[head++];
  // for each in-bounds neighbor with dist > dist[r][c] + 1:
  //   dist[nr][nc] = dist[r][c] + 1; queue.push([nr, nc]);
}
return dist;

FLASHCARDS Tap to flip

Why BFS from the 0s instead of from each 1?

BFS from each 1 is O((mn)²). One BFS seeded with all 0s touches each cell once → O(mn).

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the multi-source BFS solution?

QUESTION 02

Why seed the queue with the 0-cells instead of the 1-cells?

QUESTION 03

For mat=[[0,0,0],[0,1,0],[1,1,1]], what is the output cell at (2,1)?

QUESTION 04

Why is the distance assigned to a cell the first time BFS reaches it already optimal?

QUESTION 05

What is the space complexity of the BFS solution (excluding the output grid)?

QUESTION 06

Which alternative achieves O(1) extra space (besides the output)?

QUESTION 07

A common bug is to use the single input grid for both distances and the visited check. Why does that fail?

QUESTION 08

#542 · 01 MatrixCompute each cell’s distance to the nearest 0 by seeding a BFS queue with every 0 at once and expanding outward — the first time a cell is reached is its shortest distance. O(m·n), versus a two-pass DP alternative.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Invert the search: BFS from the zeros, not the ones

RECIPE Seed all zeros, flood outward

COST Complexity & alternatives

The two-pass DP alternative

RUN IT Multi-source BFS outward from every 0

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Multi-source BFS

ALT 1 Two-pass dynamic programming

ALT 2 BFS from every 1 (brute force)

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _