542. 01 Matrix

Medium

---

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.

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

• n == mat[i].length

• 1 <= m, n <= 104

• 1 <= m * n <= 104

• mat[i][j] is either 0 or 1.

• There is at least one 0 in mat.

Solution

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        row = len(mat)
        col = len(mat[0])
        distance = [[None]*col for _ in range(row)]
        dq = deque()
        for i in range(row):
            for j in range(col):
                if not mat[i][j]:
                    distance[i][j] = 0 # Putting All Zeroes first and then visit its adjacent
                    dq.append((i,j))
        while dq:
            i,j = dq.popleft()
            # This None Check in All is to check if it has not been visited yet
            if (i-1) >= 0 and distance[i-1][j] is None:
                distance[i-1][j] = distance[i][j] + 1
                dq.append((i-1,j)) # Now push it so that we can visit its adjacent ones
            if (j-1) >= 0 and distance[i][j-1] is None:
                distance[i][j-1] = distance[i][j] + 1
                dq.append((i,j-1)) # Now push it so that we can visit its adjacent ones
            if (i+1) < row and distance[i+1][j] is None:
                distance[i+1][j] = distance[i][j] + 1
                dq.append((i+1,j)) # Now push it so that we can visit its adjacent ones
            if (j+1) < col and distance[i][j+1] is None:
                distance[i][j+1] = distance[i][j] + 1
                dq.append((i,j+1)) # Now push it so that we can visit its adjacent ones
        
        return distance