542. 01 Matrix - Detailed Explanation

Problem Statement

You are given an m × n binary matrix mat where each cell is either 0 or 1. Return a matrix dist of the same dimensions where dist[i][j] is the distance from cell (i,j) to the nearest 0 in mat. Distance is measured in number of moves in the four cardinal directions.

Input

• mat: an array of m rows each with n integers (0 or 1)

Output

• dist: an m × n matrix of integers

Examples

Example 1
Input
mat = [
  [0,0,0],
  [0,1,0],
  [0,0,0]
]
Output
[
  [0,0,0],
  [0,1,0],
  [0,0,0]
]

Example 2
Input
mat = [
  [0,0,0],
  [0,1,0],
  [1,1,1]
]
Output
[
  [0,0,0],
  [0,1,0],
  [1,2,1]
]

Constraints

• 1 ≤ m, n ≤ 10⁴
• m × n ≤ 10⁵
• mat[i][j] is 0 or 1

Intuition

For each 1‑cell, we need the shortest path to any 0‑cell. Rather than running a separate BFS from each 1 (which would be O(m n × m n)), we can start BFS simultaneously from all 0’s (multi‑source BFS). Alternatively, a two‑pass DP also computes the minimum distance.

Approach 1 Multi‑Source BFS

Explanation

1. Enqueue all coordinates of 0‑cells and mark their distance as 0.
2. Initialize distance of 1‑cells to infinity (or a large sentinel).
3. Perform BFS: at each step, pop a cell, look at its four neighbors. If neighbor’s current dist > current dist + 1, update it and enqueue.
4. Continue until the queue is empty.

This guarantees each 1‑cell’s dist is set the first time it’s reached via the shortest path from any zero.

Step‑by‑Step Walkthrough

mat = [
 [0,1,1],
 [1,1,1],
 [1,1,0]
]

• Start queue with (0,0) and (2,2), dist=0 there.
• First expand (0,0): update (1,0) and (0,1) to 1.
• Expand (2,2): update (1,2) and (2,1) to 1.
• Continue BFS layer by layer, filling in 2’s for the remaining 1’s.

Approach 2 Two‑Pass Dynamic Programming

Explanation

Use DP with two sweeps:

1. Top‑Left to Bottom‑Right

   if mat[i][j] == 0: dist[i][j]=0
   else:
     dist[i][j] = min(
       dist[i-1][j] + 1 if i>0 else inf,
       dist[i][j-1] + 1 if j>0 else inf
     )
   

2. Bottom‑Right to Top‑Left
   Update similarly using neighbors below and to the right:

   if mat[i][j] != 0:
     dist[i][j] = min(dist[i][j],
       dist[i+1][j] + 1 if i<m-1 else inf,
       dist[i][j+1] + 1 if j<n-1 else inf
     )
   

After both passes, dist[i][j] holds the shortest distance to a zero.

Complexity Analysis

Time

• BFS approach: O(m × n) since each cell is enqueued/dequeued once
• DP approach: O(m × n) for two full passes

Space

• O(m × n) for the distance matrix and queue (BFS) or just the dist matrix (DP)

Common Mistakes

• Not initializing 1‑cells to a large value before BFS or DP
• Forgetting to check bounds when visiting neighbors
• Using ordinary BFS from each 1‑cell instead of multi‑source BFS

Edge Cases

• All zeros → output is all zeros
• All ones → BFS will fill increasing distances outward until matrix ends
• Single row or single column → still works with both methods

Python