LeetCode · #542
01 Matrix Solution
Given a binary matrix, return a matrix where each cell stores the distance to the nearest 0. This is a classic multi-source BFS problem: all zero cells are starting points at distance 0.
01
Section One · Problem
Problem Statement
Each matrix cell is a vertex. From a cell, you can move up, down, left, or right. The question asks for the shortest path from every 1 cell to any 0 cell. Because all zeros are equally valid targets, the best trick is to reverse the perspective: start BFS from all zeros simultaneously and let distances spread outward.
Example
Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
// center bottom cell is 2 steps away from the nearest zero
Constraints
• 1 ≤ m, n ≤ 10⁴, with m · n ≤ 10⁴ • mat[i][j] is either 0 or 1 • There is at least one 0 in the matrix
02
Section Two · Brute Force
Run a BFS from Every 1 Cell — O((m·n)²)
For each cell containing 1, launch a fresh BFS until you hit a 0. Because BFS explores by increasing distance, the first zero you reach is the nearest one for that starting cell.
Why it works
A single-source BFS in an unweighted grid always finds shortest path length. Repeating that search for every 1 cell produces correct distances independently.
Problem: Adjacent
1 cells recompute almost the same search space again and again. If the matrix has many ones, we keep paying for overlapping BFS traversals. The optimal solution shares all that work in one pass.
Java — BFS from each 1 cell
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public int[][] updateMatrix(int[][] mat) {
int rows = mat.length, cols = mat[0].length;
int[][] answer = new int[rows][cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (mat[r][c] == 0) continue;
answer[r][c] = distanceToNearestZero(mat, r, c);
}
}
return answer;
}
private int distanceToNearestZero(int[][] mat, int sr, int sc) {
int rows = mat.length, cols = mat[0].length;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] { sr, sc, 0 });
visited[sr][sc] = true;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
if (mat[cell[0]][cell[1]] == 0) return cell[2];
for (int[] dir : DIRS) {
int nr = cell[0] + dir[0];
int nc = cell[1] + dir[1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || visited[nr][nc]) continue;
visited[nr][nc] = true;
queue.offer(new int[] { nr, nc, cell[2] + 1 });
}
}
return -1;
}
}
Python — BFS from each 1 cell
from collections import deque
class Solution:
def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
rows, cols = len(mat), len(mat[0])
answer = [[0] * cols for _ in range(rows)]
def distance_to_zero(sr: int, sc: int) -> int:
queue = deque([(sr, sc, 0)])
visited = {(sr, sc)}
while queue:
r, c, dist = queue.popleft()
if mat[r][c] == 0:
return dist
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
continue if (nr, nc) in visited:
continue
visited.add((nr, nc))
queue.append((nr, nc, dist + 1))
return -1 for r in range(rows):
for c in range(cols):
if mat[r][c] == 1:
answer[r][c] = distance_to_zero(r, c)
return answer
03
Section Three · Optimal
Multi-Source BFS from Every 0 — O(m·n)
Instead of asking, “How far is each 1 from a zero?”, ask the reverse: “How far does each zero spread into the matrix?” Put all zero cells in the queue with distance 0, then BFS outward. The first time a cell is reached is its shortest distance to any zero.
💡 Mental model: Imagine every zero cell is a radio tower broadcasting a signal at time 0. Every minute, the signal reaches one step farther. The first signal to reach a cell is automatically the closest tower, so that arrival time is exactly the answer for that cell.
Algorithm
- Initialize a queue with every
0cell. - Set all
1cells to a sentinel like-1in the answer grid to mark them unvisited. - Pop a cell from the queue and inspect its four neighbors.
- If a neighbor is still unvisited, assign
answer[nr][nc] = answer[r][c] + 1and enqueue it. - Because BFS explores in distance order, the first assigned distance is optimal.
🎯 Recognition pattern:
- If a problem asks for the nearest source, shortest distance to any target, or minimum time from many starting points, try multi-source BFS.
- Related problems: LC 994 Rotting Oranges, LC 286 Walls and Gates, LC 1162 As Far from Land as Possible.
Why not DFS?:
- DFS does not respect increasing distance order.
- It may reach a cell through a longer path before a shorter path, which means you need extra relaxation logic.
- BFS layers already encode shortest path in an unweighted grid.
04
Section Four · Walkthrough
Visual Walkthrough
01 Matrix — expand outward from all zeros at once
05
Section Five · Code
Code — Java & Python
Java — multi-source BFS
import java.util.ArrayDeque;
import java.util.Queue;
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public int[][] updateMatrix(int[][] mat) {
int rows = mat.length, cols = mat[0].length;
int[][] dist = new int[rows][cols];
Queue<int[]> queue = new ArrayDeque<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (mat[r][c] == 0) {
queue.offer(new int[] { r, c });
dist[r][c] = 0;
} else {
dist[r][c] = -1; // unvisited 1-cell
}
}
}
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] dir : DIRS) {
int nr = cell[0] + dir[0];
int nc = cell[1] + dir[1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (dist[nr][nc] != -1) continue;
dist[nr][nc] = dist[cell[0]][cell[1]] + 1;
queue.offer(new int[] { nr, nc });
}
}
return dist;
}
}
Python — multi-source BFS
from collections import deque
class Solution:
def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
rows, cols = len(mat), len(mat[0])
dist = [[-1] * cols for _ in range(rows)]
queue = deque()
for r in range(rows):
for c in range(cols):
if mat[r][c] == 0:
dist[r][c] = 0
queue.append((r, c))
while queue:
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
continue if dist[nr][nc] != -1:
continue
dist[nr][nc] = dist[r][c] + 1
queue.append((nr, nc))
return dist
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| BFS from each 1 cell | O((m · n)²) | O(m · n) | Conceptually simple, but repeats almost identical searches many times. |
| Multi-source BFS ← optimal | O(m · n) | O(m · n) | Each cell enters the queue at most once, so all nearest-zero distances are filled in one traversal. |
Core reason it is linear:
- every cell is assigned exactly once.
- Once
dist[r][c]is no longer-1, that cell will never be enqueued again.
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Expected behavior | Why it matters |
|---|---|---|
| All zeros | Return all zeros immediately | The initial queue already contains every cell. |
| Single one next to zero | Distance is 1 | Sanity-checks the basic neighbor expansion. |
| Long corridor of ones | Distances increase layer by layer | Shows why BFS layers naturally model shortest path distance. |
| Many zeros | Start from all of them together | Running separate BFS from each zero would duplicate work. |
| Visited marked too late | May enqueue the same cell many times | Always assign distance before enqueueing. |
⚠ Common Mistake: Starting a BFS from every
1 or every 0 separately. The winning insight is that all zeros can share one queue. Another common bug is forgetting a sentinel like -1 for unvisited 1 cells, which makes it hard to distinguish “distance 0 because this is a zero” from “not processed yet”.