Log inSign up
mediumLeetCodeNot Started

01 Matrix

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1 · Standard 3x3 Matrix:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]
Explanation: The center cell 1 has distance 1 to all surrounding 0s.

Example 2 · Matrix with Distances > 1:

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]
Explanation: The bottom-center cell is at Manhattan distance 2 from the nearest 0.

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.
  • There is at least one 0 in mat.

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Queue data structure & standard BFS traversal
  • 2D matrix coordinate navigation and boundary checking
  • Multi-source graph shortest path fundamentals

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the multi-source BFS pattern for simultaneous shortest path expansion.
  • Understand the 2-pass dynamic programming technique on 2D grids (directional decomposition).
  • Properly implement 4-directional grid boundary checks.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Input structure involves an array or contiguous sequence with constraints on element relationships.
  • Optimal solution requires avoiding O(N2) exhaustive searches through state tracking or pointers.
  • Subproblem exhibits optimal substructure or monotonicity enabling linear or logarithmic processing.

Algorithmic Decision Tree:

  • If the array is sorted or can be sorted without violating problem requirements, evaluate Two Pointers or Binary Search.
  • If tracking contiguous subsegments with monotone expansion/shrinkage, apply Sliding Window.
  • If frequency or complement lookups are required in O(1) time, use a Hash Map or Frequency Array.

Connected Patterns:

Rotting OrangesShortest BridgeAs Far from Land as Possible

1. BFS from Every Cell (Brute Force)

Intuition

Iterate through every cell (r, c). If mat[r][c] == 0, distance is 0. If mat[r][c] == 1, launch a breadth-first search expanding outwards until the first 0 is reached.

When to apply: Use to understand the shortest-path distance problem.

Individual BFS Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 0, 0, 0, 1, 0, 1, 1, 1]
Current operationSTEP 1 OF 6
Input grid: row 0 is [0, 0, 0], row 1 is [0, 1, 0], row 2 is [1, 1, 1]
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
0
↑ 0s
0
0
r1
0
1
0
r2
1
1
1
Variables at this step
zeroCells
["(0,0)","(0,1)","(0,2)","(1,0)","(1,2)"]
Check / comparison
Zero cells identified.
Decision / next transition
dist[r][c] = 0 for all cells with value 0.
Why this step matters

Input grid: row 0 is [0, 0, 0], row 1 is [0, 1, 0], row 2 is [1, 1, 1]. All 0 cells have distance 0.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[][] updateMatrix(int[][] mat) {
6 int m = mat.length, n = mat[0].length;
7 int[][] dist = new int[m][n];
8 int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
9
10 for (int r = 0; r < m; r++) {
11 for (int c = 0; c < n; c++) {
12 if (mat[r][c] == 0) continue;
13 Queue<int[]> q = new LinkedList<>();
14 q.add(new int[]{r, c, 0});
15 boolean[][] visited = new boolean[m][n];
16 visited[r][c] = true;
17
18 while (!q.isEmpty()) {
19 int[] curr = q.poll();
20 if (mat[curr[0]][curr[1]] == 0) {
21 dist[r][c] = curr[2];
22 break;
23 }
24 for (int[] d : dirs) {
25 int nr = curr[0] + d[0], nc = curr[1] + d[1];
26 if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc]) {
27 visited[nr][nc] = true;
28 q.add(new int[]{nr, nc, curr[2] + 1});
29 }
30 }
31 }
32 }
33 }
34 return dist;
35 }
36 }
37
38 public static void main(String[] args) {
39 Solution sol = new Solution();
40 int[][] mat = {
41 {0, 0, 0},
42 {0, 1, 0},
43 {1, 1, 1}
44 };
45 System.out.println("Distances: " + Arrays.deepToString(sol.updateMatrix(mat)));
46 }
47}

Time & Space Complexity

  • Time complexity: O((m * n)^2) — For up to m*n cells, each BFS can explore all m*n cells in the worst case.
  • Space complexity: O(m * n) — Queue and visited matrix for BFS.

Why Brute Force Doesn't Scale:

For a 100x100 matrix (10,000 cells), naive BFS takes ~100,000,000 operations.

Multi-Source BFS touches each cell and edge at most 4 times, completing in ~40,000 operations (2,500x speedup).

2. Multi-Source BFS from All Zeroes

Intuition

1. Initialize dist matrix with -1. 2. Enqueue all cells with mat[r][c] == 0 and set dist[r][c] = 0. 3. While queue is not empty, pop (r, c). For each 4-directional neighbor (nr, nc): if dist[nr][nc] == -1, set dist[nr][nc] = dist[r][c] + 1 and enqueue (nr, nc).

When to apply: Use as the standard graph shortest-path approach for multiple source targets.

Multi-Source BFS Level Expansion Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 0, 0, 0, 1, 0, 1, 1, 1]
Current operationSTEP 1 OF 6
Enqueue all 0 cells: (0,0), (0,1), (0,2), (1,0), (1,2)
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
0
↑ 0s
0
0
r1
0
-1
0
r2
-1
-1
-1
Variables at this step
queueSize
5
Check / comparison
Sources enqueued.
Decision / next transition
Queue initialized with 5 source cells.
Why this step matters

Enqueue all 0 cells: (0,0), (0,1), (0,2), (1,0), (1,2). Set their dist = 0. All 1s initialized to -1.

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[][] updateMatrix(int[][] mat) {
6 int m = mat.length, n = mat[0].length;
7 int[][] dist = new int[m][n];
8 Queue<int[]> q = new LinkedList<>();
9
10 for (int r = 0; r < m; r++) {
11 for (int c = 0; c < n; c++) {
12 if (mat[r][c] == 0) {
13 q.add(new int[]{r, c});
14 } else {
15 dist[r][c] = -1;
16 }
17 }
18 }
19
20 int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
21 while (!q.isEmpty()) {
22 int[] curr = q.poll();
23 for (int[] d : dirs) {
24 int nr = curr[0] + d[0], nc = curr[1] + d[1];
25 if (nr >= 0 && nr < m && nc >= 0 && nc < n && dist[nr][nc] == -1) {
26 dist[nr][nc] = dist[curr[0]][curr[1]] + 1;
27 q.add(new int[]{nr, nc});
28 }
29 }
30 }
31 return dist;
32 }
33 }
34
35 public static void main(String[] args) {
36 Solution sol = new Solution();
37 int[][] mat = {
38 {0, 0, 0},
39 {0, 1, 0},
40 {1, 1, 1}
41 };
42 System.out.println("Distances: " + Arrays.deepToString(sol.updateMatrix(mat)));
43 }
44}

Time & Space Complexity

  • Time complexity: O(m * n) — Every cell is enqueued and visited at most once.
  • Space complexity: O(m * n) — Queue and distance matrix hold m*n elements.

3. Two-Pass Dynamic Programming (Optimal & O(1) Auxiliary)

Intuition

1. Pass 1 (Top-Left -> Bottom-Right): For each cell with mat[r][c] != 0, dist[r][c] = min(dist[r-1][c], dist[r][c-1]) + 1. 2. Pass 2 (Bottom-Right -> Top-Left): dist[r][c] = min(dist[r][c], min(dist[r+1][c], dist[r][c+1]) + 1). This propagates minimum distance from all four directions in two linear passes.

When to apply: Use to avoid extra queue memory overhead while maintaining O(m * n) time.

Two-Pass DP Propagation Trace

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
InputINPUT nums = [0, 0, 0, 0, 1, 0, 1, 1, 1]
Current operationSTEP 1 OF 6
Pass 1 (Top-Left): Cells with 0 stay 0
Visual state
Values and pointers at this exact step
matrix
c0
c1
c2
r0
0
0
0
r1
0
INF
↑ Init
0
r2
INF
INF
INF
Variables at this step
pass
1
Check / comparison
Start Pass 1.
Decision / next transition
Initialize DP grid.
Why this step matters

Pass 1 (Top-Left): Cells with 0 stay 0. Cells with 1 initialize to large INF (e.g. 10000).

Step 1 / 6
JAVA SOLUTIONCLEAN & OPTIMIZED
1import java.util.*;
2
3public class Main {
4 public static class Solution {
5 public int[][] updateMatrix(int[][] mat) {
6 int m = mat.length, n = mat[0].length;
7 int INF = m + n;
8 int[][] dist = new int[m][n];
9
10 // Pass 1: Top-Left to Bottom-Right
11 for (int r = 0; r < m; r++) {
12 for (int c = 0; c < n; c++) {
13 if (mat[r][c] == 0) {
14 dist[r][c] = 0;
15 } else {
16 dist[r][c] = INF;
17 if (r > 0) dist[r][c] = Math.min(dist[r][c], dist[r - 1][c] + 1);
18 if (c > 0) dist[r][c] = Math.min(dist[r][c], dist[r][c - 1] + 1);
19 }
20 }
21 }
22
23 // Pass 2: Bottom-Right to Top-Left
24 for (int r = m - 1; r >= 0; r--) {
25 for (int c = n - 1; c >= 0; c--) {
26 if (r < m - 1) dist[r][c] = Math.min(dist[r][c], dist[r + 1][c] + 1);
27 if (c < n - 1) dist[r][c] = Math.min(dist[r][c], dist[r][c + 1] + 1);
28 }
29 }
30 return dist;
31 }
32 }
33
34 public static void main(String[] args) {
35 Solution sol = new Solution();
36 int[][] mat = {
37 {0, 0, 0},
38 {0, 1, 0},
39 {1, 1, 1}
40 };
41 System.out.println("Distances: " + Arrays.deepToString(sol.updateMatrix(mat)));
42 }
43}

Time & Space Complexity

  • Time complexity: O(m * n) — Two simple matrix iterations visiting each cell exactly twice.
  • Space complexity: O(1) auxiliary — Distances updated directly in result matrix.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Individual BFS per Cell with 1O((M * N)^2)O(M * N)For every cell with mat[r][c] == 1, launch a separate BFS queue to locate the closest 0.Repeated grid traversals for every single 1.
2.Better — 2-Pass Dynamic ProgrammingO(M * N)O(1)Pass 1 (top-left to bottom-right): dist[r][c] = min(dist[r-1][c] + 1, dist[r][c-1] + 1). Pass 2 (bottom-right to top-left): dist[r][c] = min(dist[r][c], dist[r+1][c] + 1, dist[r][c+1] + 1).Two grid traversals.
3.Optimal — Multi-Source BFSOptimalO(M * N)O(M * N)Push all coordinates with value 0 into a single BFS queue with distance 0. Mark all 1s as unvisited. Pop and relax unvisited 4-directional neighbors.None; optimal.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Empty or Single Element Array — Handle minimal input sizes (N = 0 or N = 1) cleanly without out-of-bounds errors.
  • Duplicate Elements — Verify behavior when all elements are identical (e.g. all 0s or all equal values).
  • Extreme Numerical Values — Account for maximum/minimum allowed constraint values (-109 to 109) to prevent overflow.
  • Boundary Conditions — Ensure correct execution when target or match is located at the first or last index.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always state the brute force baseline before presenting the optimal solution to demonstrate structured problem solving.
  2. Explicitly verify boundary conditions (empty arrays, single elements, duplicates, extremes) out loud with the interviewer.
  3. Analyze both time and auxiliary space complexities clearly, explaining trade-offs between speed and memory allocation.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for 01 Matrix?

2.Why is the brute force approach suboptimal for large inputs in 01 Matrix?

3.Which data structure or technique enables the optimal solution for 01 Matrix?

Back to DSA Sheet