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]] 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:
m == mat.lengthn == mat[i].length1 <= m, n <= 1041 <= m * n <= 104mat[i][j] is either 0 or 1.0 in mat.
Note: This question is the same as 1765: https://leetcode.com/problems/map-of-highest-peak/
The BFS approach involves initializing a queue with all positions of zeros in the matrix, since the distance from any zero to itself is zero. From there, perform a level-order traversal (BFS) to update the distances of the cells that are accessible from these initial zero cells. This approach guarantees that each cell is reached by the shortest path.
In the C implementation, we use a queue to perform a BFS starting from all cells with 0. We then update neighboring cells with the smallest distance possible, propagating the minimum distances to eventually fill out the entire matrix with correct values.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n), as each cell is processed at most once.
Space Complexity: O(m * n), for storing the resulting distance matrix and the BFS queue.
The dynamic programming (DP) approach updates the matrix by considering each cell from four possible directions, iterating twice over the matrix to propagate the minimum distances. First, traverse from top-left to bottom-right, and then from bottom-right to top-left, ensuring a comprehensive minimum distance calculation.
In this C code, distance calculation progresses first from the top-left to bottom-right. We then perform a second pass from bottom-right to top-left to integrate the shortest distances possible from alternate directions. The use of INT_MAX - 1 is a sufficient surrogate for infinity.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m * n)
Space Complexity: O(m * n)
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(m * n), as each cell is processed at most once. |
| Dynamic Programming Approach | Time Complexity: O(m * n) |
G-13. Distance of nearest cell having 1 | 0/1 Matrix | C++ | Java • take U forward • 295,156 views views
Watch 9 more video solutions →Practice 01 Matrix with our built-in code editor and test cases.
Practice on FleetCode