LeetCode #542 Medium

01 Matrix

For a grid of 0s and 1s, return the distance from each cell to its nearest 0.

bfsgridmulti-source

02

Intuition

The obvious plan is to run a BFS from every 1 out to the nearest 0, but that repeats work across cells and costs O(cells^2). Flip the direction: push every 0 into the queue at once, at distance 0, and BFS outward from all of them simultaneously. Because BFS explores in increasing distance order, the very first time the combined wave reaches a cell is guaranteed to be via the shortest possible path to any 0. One sweep fills in every distance, and no cell is ever revisited once set.

How to spot this pattern

Multi-source BFS from every zero simultaneously. Because all sources start at distance 0, the wave reaches each cell by its shortest route automatically — no per-cell comparison needed, and dist doubles as the visited marker.

03

Approach

1

Seed with every 0

Scan the grid once. Every cell holding 0 gets distance 0 and is pushed into the BFS queue immediately, rather than starting one BFS per 1.

2

Multi-source BFS

Process the queue level by level. For each popped cell, look at its 4 neighbors; any neighbor that has not been assigned a distance yet gets current distance + 1 and is pushed.

3

Why first-touch is shortest

BFS visits cells in nondecreasing distance order from the combined source set. The first time any cell is reached, that path length is minimal, so no cell needs a second visit or a distance update.

04

Solution & live demo

▶1class Solution:
▶2    def updateMatrix(self, mat):
▶3        from collections import deque
▶4        R, C = len(mat), len(mat[0])
▶5        dist = [[None] * C for _ in range(R)]
▶6        q = deque()
▶7        for r in range(R):
▶8            for c in range(C):
▶9                if mat[r][c] == 0:
▶10                    dist[r][c] = 0
▶11                    q.append((r, c))
▶12        while q:
▶13            r, c = q.popleft()
▶14            for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
▶15                if 0 <= nr < R and 0 <= nc < C and dist[nr][nc] is None:
▶16                    dist[nr][nc] = dist[r][c] + 1
▶17                    q.append((nr, nc))
▶18        return dist

05

Common pitfalls

Running BFS from each 1

✗ Wrong

for each cell with 1: bfs to nearest 0

✓ Right

for each cell with 0: q.append((r, c))

That's a separate search per cell — O((RC)²) in the worst case. Seeding every zero at distance 0 computes all answers in one pass over the grid.

Using a separate visited array

✗ Wrong

visited = [[False] * C for _ in range(R)]

✓ Right

dist[nr][nc] is None

None in the distance grid already means unvisited, so a second structure is redundant bookkeeping that can drift out of sync. The first write is also the visit mark.

Writing the distance when dequeuing

✗ Wrong

r, c = q.popleft()
dist[r][c] = ...

✓ Right

dist[nr][nc] = dist[r][c] + 1
q.append((nr, nc))

A cell reachable from two sources gets enqueued twice before either is processed, so the second entry overwrites with a larger distance. Marking at enqueue time admits each cell exactly once, at its true minimum.

06

Edge cases

Grid is all 0s

Every cell is a source with distance 0; nothing is enqueued.

A single 1 surrounded by 0s

It is reached in the very first layer, distance 1.

1x1 grid

Either [[0]] (distance 0) since at least one 0 is guaranteed to exist.

Large block of 1s

Distances grow with BFS depth from the nearest border of 0s, still one pass.

07

Complexity

Time

O(R*C)

Space

O(R*C)

Every cell enqueued and dequeued once, versus O(cells^2) for a BFS-per-1.