01 Matrix
Problem Description
Question
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two cells sharing a common edge is 1.
Example 1:
Input:mat=[[0,0,0],[0,1,0],[0,0,0]]
0
1
2
0
0
0
0
1
0
1
0
2
0
0
0
Output:[[0,0,0],[0,1,0],[0,0,0]]
0
1
2
0
0
0
0
1
0
1
0
2
0
0
0
Example 2:
Input:mat=[[0,0,0],[0,1,0],[1,1,1]]
0
1
2
0
0
0
0
1
0
1
0
2
1
1
1
Output:[[0,0,0],[0,1,0],[1,2,1]]
0
1
2
0
0
0
0
1
0
1
0
2
1
2
1
Constraints:
m == mat.lengthn == mat[i].length- 1 <= m, n <= 104
- 1 <= m * n <= 104
mat[i][j]is either0or1.- There is at least one
0inmat.
Solve it on LeetCode
Approaches
1. Breadth-First Search (BFS) from Zeros
Intuition:
- The problem requires finding the shortest distance from each cell containing
1to the nearest cell containing0. - A natural way to explore distances outward from source points (0's) is via a BFS, as BFS by nature explores equally in all directions level-by-level.
- Initialize the distance to
0for all cells containing0. - Enqueue all
0cells initially and start the BFS. - For each dequeued cell, update its neighboring cells if a shorter distance is discovered.
Steps:
- Initialize a queue structure and set distances according to the input matrix — zero for
0cells, infinity for1cells. - Add all zeros to a queue.
- Perform a BFS where each cell updates its neighbors with its distance plus one, provided the neighbor's current value is greater than the newly proposed distance.
- Continue until processing for all cells is complete.
Code:
Complexity Analysis
- Time Complexity: O(m * n), where
mandnare the matrix dimensions. Each cell is processed at most once. - Space Complexity: O(m * n), needed for the distance matrix and the BFS queue.
2. Dynamic Programming Approach
Intuition:
- The idea is to use DP to find optimal substructure — checking paths dynamically based on previously computed paths.
- Since BFS from each zero can be suboptimal and cumbersome for large inputs, consider updating the distances recursively based on dynamic programming.
- Traverse the matrix two times: once from top-left to bottom-right, and again from bottom-right to top-left, to ensure that the shortest path from any direction is captured.
Steps:
- Initialize the distance array with infinite places for
1initially. - Traverse the matrix from the top-left, filling out shortest distances leveraging known zero positions and dynamic table values.
- Traverse again from the bottom-right, updating the table further to reflect any shorter distances by considering the bottom-right-to-top-left direction.
Code:
Complexity Analysis
- Time Complexity: O(m * n), the matrix is traversed twice.
- Space Complexity: O(1), only a fixed amount of extra space used, modifying the input.