Problem Statement

Given an m x n matrix mat containing only 0 and 1, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells of mat is 1.

Examples

Example 1:

• Input: mat =

[[1,0,1,1],
 [1,1,1,1],
 [1,1,1,0]]

• Expected Output:

[[1,0,1,2],
 [2,1,2,1],
 [3,2,1,0]]

• Justification: Each cell updates to the minimum distance to a zero, with the edges being closest and moving inward, the distance increases.

Example 2:

• Input: mat =

[[0,1,1],
 [1,1,0],
 [1,0,1]]

• Expected Output:

[[0,1,1],
 [1,1,0],
 [1,0,1]]

• Justification: Starting with the zeros, we update their neighbors. The zeros remain zeros since they are already at the nearest zero. The ones directly adjacent to a zero become ones, demonstrating their proximity.

Example 3:

• Input: mat =

[[1,1,0],
 [0,1,1],
 [1,1,1]]

• Expected Output:

[[1,1,0],
 [0,1,1],
 [1,2,2]]

• Justification: Output matrix represents the shortest path to a zero for each cell.

Constraints:

• 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.

Try it yourself

Try solving this question here: