medium

01 Matrix

Find the distance from every cell in a grid to its nearest zero.

1. Define the problem

01 Matrix

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell, where the distance between two adjacent cells is 1. Seed the queue with every 0 at once — this is multi-source breadth-first search , so the ring that first reaches a cell always belongs to that cell's nearest 0, not just one particular 0.

Constraints

  • m == mat.length
  • n == mati.length
  • 1 ≤ m, n ≤ 104
  • 1 ≤ m * n ≤ 104
  • mati[j] is 0 or 1
  • There is at least one 0 in mat

Example

Inputmat = [[0, 0, 0], [0, 1, 0], [1, 1, 1]]
Output[[0, 0, 0], [0, 1, 0], [1, 2, 1]]

Explanation The bottom row is at distance 1 or 2 from the nearest 0 in the top two rows.

2. Know the words first

In plain terms

Multi-source
Starting the search from several places at the same time, instead of just one, so they all expand outward together.
3. Visualize the solution

One cell per matrix cell, row by row — each shows its distance to the nearest 0

One cell per matrix cell, row by row — each shows its distance to the nearest 0
Statusring 0

Seed the queue with every 0 at once — in this matrix that is (0,0) and (0,1), both at distance 0.

What happens in this step

mat = [[0,0,1],[1,1,1]]
queue = [(0,0),(0,1)]   both at dist = 0

Every 0 cell is a source and enters the queue in the same first pass — that's multi-source BFS.
The four 1 cells have no distance yet, so their slots show —.
Step 1 of 4

Steps to visualize

  1. This walkthrough uses a smaller matrix than the example above so the whole thing fits in one row: mat = [[0, 0, 1], [1, 1, 1]].
  2. The row has one slot per matrix cell, read left to right then down. A slot shows — until a distance has been worked out for it.
  3. Mark every 0 as distance 0 and enqueue all of them at once.
  4. Dequeue a cell; for each neighbor that hasn't been assigned a distance yet, set it to this cell's distance + 1 and enqueue it.
  5. Repeat until the queue is empty — every cell now holds its distance to the nearest 0.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per matrix cell, row by row — each shows its distance to the nearest 0
Statusring 0

Seed the queue with every 0 at once — in this matrix that is (0,0) and (0,1), both at distance 0.

What happens in this step

mat = [[0,0,1],[1,1,1]]
queue = [(0,0),(0,1)]   both at dist = 0

Every 0 cell is a source and enters the queue in the same first pass — that's multi-source BFS.
The four 1 cells have no distance yet, so their slots show —.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function updateMatrix(mat) {
  const rows = mat.length;
  const cols = mat[0].length;
  const dist = mat.map((row) => row.map(() => -1));
  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;
        queue.push([r, c]);
      }
    }
  }

  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  while (queue.length > 0) {
    const [r, c] = queue.shift();
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] === -1) {
        dist[nr][nc] = dist[r][c] + 1;
        queue.push([nr, nc]);
      }
    }
  }

  return dist;
}
Time
O(m * n)
Space
O(m * n)
6. Test cases

Test cases

InputExpectedCovers
mat = [[0, 0, 0], [0, 1, 0], [1, 1, 1]][[0, 0, 0], [0, 1, 0], [1, 2, 1]]example from the docstring
mat = [[0, 0], [0, 0]][[0, 0], [0, 0]]every cell is already a 0
mat = [[0]][[0]]smallest valid input, a single 0
mat = [[0, 1, 1, 1, 0]][[0, 1, 2, 1, 0]]a cell equidistant from two different 0s
mat = [[0, 1], [1, 0]][[0, 1], [1, 0]]every 1 is directly adjacent to a 0
mat = [[0, 1, 1, 1, 1]][[0, 1, 2, 3, 4]]only one 0, distances grow all the way across
mat = [[0], [1], [1]][[0], [1], [2]]a single-column grid

Keep reading