542. 01 Matrix — DSA Atlas

542

MediumGraph DFS and BFSBreadth-first searchMulti-source BFS from all zeros

01 Matrix

Given an m x n binary matrix, replace each cell with its distance to the nearest cell containing 0, where distance is the number of single steps up, down, left, or right. Cells that are already 0 have distance 0.

Open official problem prompt ↗

In plain English

Label every cell with how many steps it takes to reach the closest 0.

Picture it like this

Imagine every 0 cell lighting up at the same instant and fire spreading outward one square per second. The second at which a cell catches fire is its distance to the nearest ignition point.

Example

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Why: The center 1 is one step from a 0; the bottom-middle 1 is two steps from the nearest 0, while the bottom corners are one step away.

Constraints

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

Pattern lesson

See the pattern, then code

Multi-source BFS from all zeros

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Instead of a separate search from each 1, start the BFS from all zero cells simultaneously. The wave expands outward one ring at a time, so the first time a 1 is reached is its shortest distance.

New words, made simpleKnow these before the algorithm

Multi-source BFS: A breadth-first search seeded with many starting cells at once so distances are measured to the nearest source.
Layer / ring: All cells at the same BFS distance, processed before the next distance.
First-visit distance: Because BFS expands by distance, the first time a cell is reached is guaranteed shortest.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

BFS from each 1 separately

Recomputes overlapping distances repeatedly and is far too slow.

For each cell with a 1, run a search until a 0 is found.

Time O((m*n)^2)Space O(m*n)

Dynamic programming two-pass

Also optimal and elegant, but easy to get the two passes subtly wrong.

Sweep top-left then bottom-right taking min of neighbor+1.

Time O(m*n)Space O(1) extra

Best choiceMulti-source BFS

One clean linear pass; each cell is finalized on first visit.

Seed the queue with all zeros at distance 0 and expand outward once.

Time O(m*n)Space O(m*n)

The rule we keep true

Invariant

When a cell is dequeued, its stored distance equals its true shortest distance to any 0, because BFS dequeues cells in non-decreasing order of distance.

Why this is correct

Reasoning

All sources enter the queue at distance 0, and BFS processes cells strictly by increasing distance. The first assignment to a cell therefore uses the minimum possible number of steps, and marking with -1 until assigned prevents any later, longer path from overwriting it.

The algorithm in three movesSay these aloud before coding

1Initialize a distance grid, set 0 for zero cells and enqueue them

queue starts with all 0-cells (distance 0)

2Mark ones as unvisited (-1)

layer 1 fills cells adjacent to a 0

3Pop cells from the queue and visit unvisited neighbors

center (1,1) and (2,1) resolve to 1 then 2

4Set each neighbor's distance to current + 1 and enqueue it

5Continue until the queue empties

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readall 0 cells

2 · AskWhich cells are sources?

3 · Update statedistances of the five 0-cells set to 0, enqueued

4 · Resultqueue holds every 0

Key takeaway

The distance wave spreads outward from every 0 simultaneously across the 3x3 grid.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-11Seed sources
Every 0 gets distance 0 and enters the queue; ones stay -1 meaning unvisited.
2
Lines 12-13BFS loop
Pop the frontier cell whose distance is already final.
3
Lines 14-19Relax neighbors
Any in-bounds neighbor still at -1 gets current+1 and is enqueued exactly once.
4
Lines 20Result
The dist grid now holds every shortest distance.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A matrix that is entirely zeros -> all distances 0
A single 1 surrounded by zeros -> distance 1
A large thin 1 x n or m x 1 strip
The guaranteed presence of at least one 0 means no cell stays -1

Common beginner mistakes

Running a fresh BFS per 1, causing a time-limit exceed
Marking a cell visited only after popping instead of when enqueued, allowing duplicate longer assignments
Forgetting bounds checks on neighbors
Initializing distances to 0 for ones, which hides the unvisited state

Check your understanding

Why seed the queue with all zeros before starting, rather than one at a time?

PyPython 3 · solution.py

Optimal

1class Solution:2    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:3        from collections import deque4        m, n = len(mat), len(mat[0])5        dist = [[-1] * n for _ in range(m)]6        q = deque()7        for r in range(m):8            for c in range(n):9                if mat[r][c] == 0:10                    dist[r][c] = 011                    q.append((r, c))12        while q:13            r, c = q.popleft()14            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):15                nr, nc = r + dr, c + dc16                if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == -1:17                    dist[nr][nc] = dist[r][c] + 118                    q.append((nr, nc))19        return dist

Time complexityO(m * n)Optimized

Space complexityO(m * n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMeta

01 Matrix

01 Matrix

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS