Coding - 01 Matrix

Problem Statement

01 Matrix

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. Cells are adjacent in the four cardinal directions.

Constraints

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

Example 1

Input: mat = [ [0,2,0], [0,1,0], [0,0,1] ]

Output: [ [0,0,0], [0,1,0], [0,0,1] ]

Explanation: The nearest 0 for each cell is shown in the output matrix. For cells with 0, the distance is 0.

Example 2

Input: mat = [ [1,0,2,0], [0,0,0,1], [1,0,1,0] ]

Output: [ [0,0,0,0], [0,0,0,0], [0,0,0,0] ]

Hint

Use Breadth-First Search (BFS) to find the shortest distance from each cell to the nearest 0.