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.

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

python

▶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

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.

06

Complexity

Time

O(R*C)

Space

O(R*C)

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