01 Matrix: Multi-Source BFS for Nearest Zero

LeetCode's 01 Matrix (problem 542) is one of the cleanest examples of multi-source BFS. It is rated medium, and once you see the trick of reversing the search direction, the solution becomes obvious. Instead of asking "how far is each 1 from the nearest 0?" you ask "how far can each 0 reach?" and let BFS do the rest.

The problem

Given an m x n binary matrix where each cell is either 0 or 1, return a matrix of the same size where each cell contains the distance to the nearest 0. The distance between two adjacent cells (sharing an edge) is 1.

Input:  [[0, 0, 0],
         [0, 1, 0],
         [1, 1, 1]]

Output: [[0, 0, 0],
         [0, 1, 0],
         [1, 2, 1]]

The center cell (1,1) has distance 1 because it is adjacent to four 0-cells. The bottom-center cell (2,1) has distance 2 because the nearest 0 is two steps away.

The brute force

The naive approach: for every cell containing a 1, run a BFS outward until you hit a 0, then record that distance.

from collections import deque

def update_matrix_brute(mat):
    m, n = len(mat), len(mat[0])
    result = [[0] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            if mat[i][j] == 1:
                queue = deque([(i, j, 0)])
                visited = set()
                visited.add((i, j))
                while queue:
                    r, c, dist = queue.popleft()
                    if mat[r][c] == 0:
                        result[i][j] = dist
                        break
                    for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited:
                            visited.add((nr, nc))
                            queue.append((nr, nc, dist + 1))

    return result

This works, but each BFS can visit up to m * n cells, and you run one BFS per 1-cell. In the worst case (a matrix that is almost all 1s with a single 0 in a corner), this is O((m*n)^2). Far too slow for the constraints (up to 10,000 cells).

The key insight: reverse the search

Instead of searching outward from each 1, search outward from all 0s simultaneously. This is multi-source BFS: you initialize the queue with every 0-cell (distance 0), then expand layer by layer. Each unvisited 1-cell you reach gets its distance from the layer number.

Why does this work? BFS guarantees that the first time you reach a cell, you have found the shortest path. Since all 0-cells start in the queue at distance 0, the first time any 1-cell is reached, it must be from the closest 0-cell. You never need to revisit.

This single BFS visits every cell exactly once. Total time: O(m * n). Total space: O(m * n) for the queue and the result matrix.

Step-by-step walkthrough

Let's trace through the 3x3 example. Blue cells are sources (0-cells). Yellow cells are waiting to be reached. Green cells are being filled in the current layer.

The BFS completes in just 2 layers for this example. For larger matrices, the number of layers equals the maximum distance in the output.

The code

from collections import deque

def update_matrix(mat):
    m, n = len(mat), len(mat[0])
    dist = [[0] * n for _ in range(m)]
    queue = deque()

    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                queue.append((i, j))
            else:
                dist[i][j] = float("inf")

    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] > dist[r][c] + 1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))

    return dist

Let's break this down:

1. Create a dist matrix. Set 0-cells to distance 0 and add them to the queue. Set 1-cells to infinity (unvisited).
2. Process the queue. For each cell, check its four neighbors. If a neighbor's current distance is greater than dist[r][c] + 1, update it and add the neighbor to the queue.
3. The condition dist[nr][nc] > dist[r][c] + 1 ensures each cell is only enqueued when we find a shorter path, which happens exactly once per cell.
4. When the queue is empty, every cell has its minimum distance.

Alternative: dynamic programming two-pass

You can also solve this with two DP passes over the matrix. The first pass goes top-left to bottom-right, considering only the top and left neighbors. The second pass goes bottom-right to top-left, considering the bottom and right neighbors.

def update_matrix_dp(mat):
    m, n = len(mat), len(mat[0])
    dist = [[float("inf")] * n for _ in range(m)]

    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                dist[i][j] = 0
            else:
                if i > 0:
                    dist[i][j] = min(dist[i][j], dist[i-1][j] + 1)
                if j > 0:
                    dist[i][j] = min(dist[i][j], dist[i][j-1] + 1)

    for i in range(m - 1, -1, -1):
        for j in range(n - 1, -1, -1):
            if i < m - 1:
                dist[i][j] = min(dist[i][j], dist[i+1][j] + 1)
            if j < n - 1:
                dist[i][j] = min(dist[i][j], dist[i][j+1] + 1)

    return dist

This also runs in O(m * n) time and uses O(1) extra space beyond the output matrix. The DP approach avoids the overhead of a queue, making it slightly faster in practice. However, the BFS approach is more intuitive and generalizes better to problems where distances are not uniform.

Complexity analysis

Both the BFS and DP solutions are optimal in time. The DP solution wins on space if you can modify the input or reuse the output matrix.

The building blocks

This problem is built on two reusable bricks:

Multi-source BFS

The core pattern for multi-source BFS:

queue = deque()
for each source node:
    queue.append(source)
    dist[source] = 0

while queue:
    node = queue.popleft()
    for neighbor in adjacent(node):
        if dist[neighbor] > dist[node] + 1:
            dist[neighbor] = dist[node] + 1
            queue.append(neighbor)

This is the same template you use for "rotten oranges" (LeetCode 994), "walls and gates" (LeetCode 286), and any problem that asks "what is the shortest distance from any source to every other cell?"

Grid BFS neighbor traversal

The four-directional neighbor check:

for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
    nr, nc = r + dr, c + dc
    if 0 <= nr < m and 0 <= nc < n:
        ...

This is the standard grid traversal brick. You use it in flood fill, island counting, shortest path problems, and any grid BFS/DFS.

Edge cases

Before submitting, verify your solution handles:

• All zeros: every cell is already 0, so the output is all zeros. The BFS queue starts full and immediately drains with no updates.
• Single row or column: the grid is 1D. BFS still works, but the DP approach is especially clean here since you only need forward and backward passes.
• Large sparse matrix: a 100x100 grid with a single 0 in the corner. The maximum distance is 198 (the cell in the opposite corner). BFS handles this fine in O(m*n).
• Checkerboard pattern: alternating 0s and 1s. Every 1-cell has distance 1. BFS finishes in a single layer after initialization.
• All ones except one zero: worst case for the brute force, but multi-source BFS still processes every cell exactly once.

From understanding to recall

You have seen how multi-source BFS works for the 01 Matrix problem. The idea is simple: seed the queue with all zeros, expand outward, and let the BFS levels naturally compute distances. But can you write it from scratch in an interview without hesitation?

The tricky parts are small but easy to fumble under pressure: initializing 1-cells to infinity, checking dist[nr][nc] > dist[r][c] + 1 instead of using a visited set, and remembering to enqueue only when you actually update a distance. These are not hard concepts, but they require precise recall.

Spaced repetition locks this in. You write the multi-source BFS template a few times over increasing intervals. After three or four repetitions, the initialization pattern and the neighbor relaxation step become automatic. When you see a "shortest distance to nearest X" problem in an interview, you recognize it instantly and code it without second-guessing.

Related posts

• Number of Islands - The classic grid BFS/DFS problem that introduces flood fill and connected component counting
• Surrounded Regions - Another grid BFS problem where you start from the boundary and work inward
• Pacific Atlantic Water Flow - Multi-source BFS from two different boundaries, combining the results

CodeBricks breaks the multi-source BFS pattern into its reusable pieces and drills them individually. You write the queue initialization, the neighbor relaxation, and the distance update from scratch each time. When you see 01 Matrix or Rotting Oranges in an interview, the code flows without hesitation.