What pattern does 01 Matrix use?

The Pattern: BFS (Multi-Source Traversal) The Heuristic: When shortest distances to multiple sources are needed, enqueue all sources initially and perform BFS simultaneously to propagate minimum distances efficiently.

01 Matrix — BFS | AlgoDrill

Q: What is the time complexity of 01 Matrix?

O(m * n). Each cell is enqueued and processed at most once. The BFS explores all neighbors in constant time per cell, resulting in linear time relative to the number of cells.

Problem

Given a matrix mat consisting of 0s and 1s, return a matrix where each cell contains the distance to the nearest 0 in mat.

m == mat.length
n == mat[i].length
1 ≤ m, n ≤ 10⁴
1 ≤ m * n ≤ 10⁴
mat[i][j] is either 0 or 1
There is at least one 0 in mat

Example

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]

Output: [[0,0,0],[0,1,0],[1,2,1]]

The algorithm starts by enqueuing all cells containing 0, treating them as sources. Each 1 cell is initialized to infinity to represent unknown distance. The BFS then expands outward from all zero cells simultaneously, updating the distance of neighboring cells if a shorter path is found. For example, the cell at (2,1) initially set to infinity is updated to 2 after exploring neighbors, reflecting the shortest path to the nearest zero at (1,1). This multi-source BFS ensures that each cell's distance is computed optimally by exploring the grid layer by layer.

Approach

Straightforward Solution

A brute-force approach would run a BFS or DFS from every cell containing 1 to find the nearest zero, resulting in O(m^2 * n^2) time complexity, which is infeasible for large matrices.

Core Observation

The shortest distance from any cell to the nearest zero can be found by exploring the grid in layers starting from all zero cells simultaneously. This is because the distance metric is uniform (each step costs 1), making BFS the natural choice for shortest path in an unweighted grid.

Path to Optimal

Preview

The key insight is to reverse the problem: instead of searching from each 1 to find the nearest 0, start from all 0s at once and propagate distances outward…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a queue with all zero cells and set all 1 cells to infinity. Perform BFS by dequeuing a cell, checking its neighbors, and updating their distances if a shorter path is found…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each cell is enqueued and processed at most once. The BFS explores all neighbors in constant time per cell, resulting in linear time relative to the number of cells.

Space

O(m * n)

The queue can hold up to all cells in the worst case, and the matrix is updated in place. This auxiliary space is necessary to track the BFS frontier.

Solution

Python

1class Solution:
  def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
      rows, cols = len(mat), len(mat[0])
      q = deque()
5
      for r in range(rows):
          for c in range(cols):
              if mat[r][c] == 0:
                  q.append((r, c))
              else:
                  mat[r][c] = float('inf')
12
      directions = [(1,0), (-1,0), (0,1), (0,-1)]
14
      while q:
          r, c = q.popleft()
17
          for dr, dc in directions:
              nr, nc = r + dr, c + dc
20
              if 0 <= nr < rows and 0 <= nc < cols and mat[nr][nc] > mat[r][c] + 1:
                  mat[nr][nc] = mat[r][c] + 1
                  q.append((nr, nc))
24
      return mat

Step-by-Step Solution

1

Initialize Queue with Zero Cells and Mark Ones as Infinite Distance

3rows, cols = len(mat), len(mat[0])
4q = deque()
6for r in range(rows):
7    for c in range(cols):
8        if mat[r][c] == 0:
9            q.append((r, c))
10        else:
11            mat[r][c] = float('inf')

Objective

To prepare the BFS by enqueuing all zero cells as starting points and marking all one cells with infinite distance to indicate they are unvisited.

Key Insight

By treating all zero cells as simultaneous sources, the BFS can propagate distances outward efficiently. Marking one cells as infinity ensures that any update to a smaller distance is meaningful and prevents revisiting cells unnecessarily.

Interview Quick-Check

Core Logic

Enqueuing all zero cells at the start enables multi-source BFS, which finds shortest distances to zeros in a single pass.

State & Boundaries

Marking one cells as infinity distinguishes unvisited cells and allows the BFS to update distances only when a shorter path is found.

Common Pitfalls & Bugs

Failing to initialize one cells to infinity can cause incorrect distance updates or infinite loops.

2

Perform BFS to Update Distances by Exploring Neighbors

To iteratively explore neighbors of each dequeued cell, updating their distances if a shorter path is found, and enqueueing them for further exploration.

3

Return the Matrix with Updated Distances

To return the matrix after BFS completes, where each cell contains the shortest distance to the nearest zero.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 21 Critical

if 0 <= nr < rows and 0 <= nc < cols and mat[nr][nc] > mat[r][c] + 1:

Check if neighbor is within bounds and if its current distance is greater than the new possible distance.

This compound condition ensures only valid neighbors are processed and that distances are updated only when a shorter path is found, preventing redundant work and infinite loops.

Line 8 Critical

if mat[r][c] == 0:

Check if the current cell contains zero.

Identifying zero cells is critical because they serve as BFS starting points for distance propagation.

Line 9 Critical

q.append((r, c))

Add zero cells to the BFS queue as starting points.

Enqueuing all zero cells initially enables multi-source BFS, which efficiently computes shortest distances to zeros.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why does starting BFS from all zero cells simultaneously guarantee the shortest distance to the nearest zero for every cell?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct 01 Matrix from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the 01 Matrix drill

or drill a free problem

1	`class Solution:`
2	`def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:`
3	`rows, cols = len(mat), len(mat[0])`
4	`q = deque()`
5
6	`for r in range(rows):`
7	`for c in range(cols):`
8	`if mat[r][c] == 0:`
9	`q.append((r, c))`
10	`else:`
11	`mat[r][c] = float('inf')`
12
13	`directions = [(1,0), (-1,0), (0,1), (0,-1)]`
14
15	`while q:`
16	`r, c = q.popleft()`
17
18	`for dr, dc in directions:`
19	`nr, nc = r + dr, c + dc`
20
21	`if 0 <= nr < rows and 0 <= nc < cols and mat[nr][nc] > mat[r][c] + 1:`
22	`mat[nr][nc] = mat[r][c] + 1`
23	`q.append((nr, nc))`
24
25	`return mat`

3	`rows, cols = len(mat), len(mat[0])`
4	`q = deque()`
6	`for r in range(rows):`
7	`for c in range(cols):`
8	`if mat[r][c] == 0:`
9	`q.append((r, c))`
10	`else:`
11	`mat[r][c] = float('inf')`