mediumGraphsPure DSA~25 min
Distance From Each Cell to the Nearest Zero
Given a grid of readings, replace each cell with its distance to the nearest baseline cell (value 0). Baseline cells stay 0; everything else reports how many steps away the closest baseline is.
Problem
Given an m x n binary matrix mat, return a matrix where each cell holds the distance to the nearest cell containing 0, measured in 4-directional steps.
Input
An m x n binary matrix mat.
Output
An m x n matrix of nearest-zero distances.
Constraints
- 1 <= m, n <= 10^4 with m*n <= 10^4
- mat[i][j] is 0 or 1.
- At least one 0 is present.
Examples
Example 1
Input
mat = [[0,0,0],[0,1,0],[0,0,0]]
Output
[[0,0,0],[0,1,0],[0,0,0]]
The lone 1 is one step from a 0.
Example 2
Input
mat = [[0,0,0],[0,1,0],[1,1,1]]
Output
[[0,0,0],[0,1,0],[1,2,1]]
Each 1 reports its shortest hop to a 0.