01 Matrix

You are given an m x n grid mat in which every cell holds either 0 or 1, and at least one cell holds 0.

Return a grid of the same size where each cell contains the distance from that cell to the nearest 0 in mat. Distance is counted in steps between cells that share an edge (up, down, left or right; no diagonals), so a cell that is itself 0 has distance 0 and a neighbour of a 0 has distance 1.

Example 1

Example 2

Example 3

Constraints

• 1 <= m, n <= 104
• 1 <= m · n <= 104
• mat[i][j] is 0 or 1
• At least one cell is 0.

Pattern Path · Graphs: Traversal · problem 129 of 169

Start simple

Run a separate BFS from each 1 until it reaches a 0 (or compare against every 0 cell): O((m·n)²) time in the worst case.

The key idea

Turn the question around. Instead of asking every 1 to find its nearest 0, let all the 0s spread outward together, one step per round. This is a multi-source BFS.

Put every 0 cell in the queue with distance 0 and mark every 1 cell as unvisited. Then process the queue in order: for each cell, look at its four neighbours, and any unvisited neighbour gets distance current + 1 and joins the queue.

Why is that distance the shortest? BFS handles cells in non-decreasing order of distance. Imagine a virtual source connected to every 0: a single BFS from it reaches each cell first along a shortest path, and starting with all 0s in the queue is exactly that. So the first time a cell is reached, the nearest 0 has claimed it, and later arrivals can only be equal or farther.

Every cell enters the queue at most once and checks four neighbours, so the work is linear in the grid size. (An alternative is two dynamic-programming sweeps, top-left to bottom-right and back.)

Complexity

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

Python

class Solution:
    def updateMatrix(self, mat):
        rows, cols = len(mat), len(mat[0])
        dist = [[-1] * cols for _ in range(rows)]  # -1 = not reached yet
        queue = deque()
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    dist[r][c] = 0
                    queue.append((r, c))  # every 0 is a starting point

        while queue:
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
        return dist

JavaScript

var updateMatrix = function(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;
        queue.push([r, c]); // every 0 is a starting point
      }
    }
  }

  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  for (let head = 0; head < queue.length; head++) {
    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;
        queue.push([nr, nc]);
      }
    }
  }
  return dist;
};

What the interviewer is checking

The key insight being tested is multi-source BFS: reversing the search direction so one traversal answers every cell, instead of one search per cell.

Mistakes to avoid

• Running BFS from each 1 separately, which is quadratic on large grids.
• Using DFS, which does not visit cells in order of distance and gives wrong (too large) answers.
• Not marking cells when they are enqueued, so they are added many times.
• Forgetting bounds checks on the grid edges.

Follow-ups to expect

• Solve it without a queue. (Two DP passes, forward then backward.)
• What if diagonal moves were allowed? (Eight neighbours in the BFS.)
• What if moving into some cells costs more? (Dijkstra with a heap.)

In real software

Image processing computes distance transforms this way (distance to the nearest edge pixel), and game maps compute distance-to-nearest-exit or -resource fields for pathfinding.

Practice next