01 Matrix — Distance to Nearest Zero via Multi-Source BFS (LC 542)

Problem Statement#

LeetCode 542 — 01 Matrix (Medium)

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.

Constraints:

• 1 <= m, n <= 10^4
• 1 <= m times n <= 10^4
• mat[i][j] is either 0 or 1.
• There is at least one 0 in the matrix.

Example:

Input:
0 0 0
0 1 0
1 1 1
 
Output:
0 0 0
0 1 0
1 2 1

Why This Problem Matters#

01 Matrix is the distance-version of Rotting Oranges and one of the most-asked Google and Amazon graph problems. The difficulty trap for candidates is that the obvious approach — BFS from every 1 to find the nearest 0 — is O((m times n)^2). The optimal approach inverts the search: BFS from every 0 outward, recording distance as the wave expands.

This single inversion (BFS from sources, not sinks) is the bedrock pattern behind LC 994, LC 286, LC 1162, LC 1102, and dozens of grid distance problems. Top interviewers explicitly probe whether you spot this inversion. If you can articulate "I will BFS from the targets to every cell because that gives me the shortest distance to any target", you move to the next round.

The Core Insight#

The shortest distance from a 1 to any 0 is the same as the shortest distance from some 0 to that 1, because the graph is undirected. So instead of running n BFS searches (one per 1), run one BFS that starts simultaneously from every 0.

When a multi-source BFS expands level by level:

• Every 0 cell has distance 0.
• Every cell at BFS level k has its nearest 0 exactly k steps away.

We use the input matrix itself for distances: initialize every 1 to a sentinel like infinity (or m + n which exceeds any possible answer), enqueue every 0, then expand. When you reach a cell whose stored distance is greater than current + 1, update and enqueue.

Why does this give correct shortest distances? BFS explores cells in non-decreasing order of distance from the seed set. The first time a cell is dequeued (or first updated), it must be the minimum distance from any seed.

Visual Dry Run#

Initial:

0 0 0
0 1 0
1 1 1

After seeding (treat 1 as infinity, denoted ∞):

0 0 0
0 ∞ 0
∞ ∞ ∞

Queue starts with every 0: [(0,0), (0,1), (0,2), (1,0), (1,2)].

Final matrix:

0 0 0
0 1 0
1 2 1

Solution (Optimal)#

Python#

from collections import deque
 
class Solution:
    def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
        R, C = len(mat), len(mat[0])
        INF = R + C                              # exceeds any reachable distance
        dist = [[INF] * C for _ in range(R)]
        queue = deque()
 
        # 1) seed queue with every 0; their distance is 0
        for r in range(R):
            for c in range(C):
                if mat[r][c] == 0:
                    dist[r][c] = 0
                    queue.append((r, c))
 
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
 
        # 2) BFS outward from all 0 sources
        while queue:
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                # only update if we found a strictly shorter path
                if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] > dist[r][c] + 1:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
 
        return dist

JavaScript#

/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function(mat) {
    const R = mat.length, C = mat[0].length;
    const INF = R + C;
    const dist = Array.from({ length: R }, () => Array(C).fill(INF));
    const queue = [];
 
    // seed with all 0 cells
    for (let r = 0; r < R; r++) {
        for (let c = 0; c < C; c++) {
            if (mat[r][c] === 0) {
                dist[r][c] = 0;
                queue.push([r, c]);
            }
        }
    }
 
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    let head = 0;                                // pointer-based dequeue is O(1)
 
    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 >= R || nc < 0 || nc >= C) continue;
            if (dist[nr][nc] > dist[r][c] + 1) {
                dist[nr][nc] = dist[r][c] + 1;
                queue.push([nr, nc]);
            }
        }
    }
    return dist;
};

Time Complexity: O(m times n) — each cell enqueued at most once. Space Complexity: O(m times n) for the distance matrix and queue.

Common Mistakes#

1. BFS from each 1 cell. This is O((m times n)^2) and times out on the constraints.
2. Forgetting the strict-inequality update. Re-enqueuing on equal distance creates redundant work; only enqueue if you strictly shortened the distance.
3. Reusing the input matrix without a sentinel. If you set 1 cells to INF directly, you mutate input — fine for LeetCode, but interview etiquette is to allocate a new dist matrix.
4. Not handling the all-zeros input. Algorithm works, but mention the edge case to show you considered it.
5. Using DFS. DFS does not yield shortest distances unless you do iterative relaxation, at which point you have re-implemented BFS poorly.

Interview Tips#

• Volunteer the inversion. Open with: "Single-source BFS from each 1 is quadratic. Multi-source BFS from every 0 is linear because the graph is undirected."
• Mention DP as an alternative. Two passes (top-left to bottom-right, then bottom-right to top-left) using min(top, left) + 1 also achieves O(m times n) without a queue. Interviewers love when you offer two valid approaches.
• Emphasize correctness. Explicitly state why BFS finds shortest distances: every cell is dequeued at its final distance because BFS explores in non-decreasing order.

Follow-up Questions#

1. What if cells have weights (not all edges are 1)? Use Dijkstra with a priority queue, multi-source seeded.
2. Can you do it without an extra matrix? Yes — overwrite mat in place. First pass marks all 1s as a large value; BFS updates them.
3. How does the two-pass DP approach work? Pass 1: for each cell, set dp[r][c] = min(dp[r-1][c], dp[r][c-1]) + 1 if cell is 1, else 0. Pass 2: scan reverse with min(dp[r+1][c], dp[r][c+1]) + 1. Final value is the answer.
4. Diagonal moves allowed? Just expand the directions array; algorithm unchanged.

Key Takeaways#

• 01 Matrix is solved by multi-source BFS from every 0, not single-source BFS from each 1.
• Inversion of source/target turns an O(N^2) problem into O(N), where N is the number of cells.
• Use a sentinel like INF = m + n to mark unvisited cells; only update when you strictly shorten the distance.
• BFS yields shortest distances in unweighted graphs because of non-decreasing exploration order.
• The DP two-pass alternative is a great backup answer in interviews to demonstrate breadth.
• This pattern generalizes to LC 994 (Rotting Oranges), LC 286 (Walls and Gates), and LC 1162 (As Far From Land).