[Search] 542. 01 Matrix

01 Matrix - LeetCode

Goal

• Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

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]]

Strategy

BFS broadcasting

• Instead of starting from 1, we start from 0 to keep track of the minimum number of steps

DP (more intuitive)

Complexity

BFS

• Time: O(mn)
• Space: O(mn)

DP

• Time: O(mn)
• Space: O(mn)

Code — BFS

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        m, n = len(mat), len(mat[0])
        DIR = [0, 1, 0, -1, 0]
q = deque([])
        for r in range(m):
            for c in range(n):
                if mat[r][c] == 0:
                    q.append((r, c))
                else:
                    mat[r][c] = -1  # Marked as not processed yet!
while q:
            r, c = q.popleft()
            for i in range(4):
                nr, nc = r + DIR[i], c + DIR[i + 1]
                if nr < 0 or nr == m or nc < 0 or nc == n or mat[nr][nc] != -1: continue
                mat[nr][nc] = mat[r][c] + 1
                q.append((nr, nc))
        return mat

Code — DP

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        r = len(mat)
        c = len(mat[0])
        
        res = [[999999 - r*c for j in i] for i in mat]
        
        for i in range(r):
            for j in range(c):
                if mat[i][j] ==0:
                    res[i][j] = 0
                else:
                    if i > 0:
                        res[i][j] = min(res[i][j], res[i-1][j]+1)
                    if j > 0:
                        res[i][j] = min(res[i][j], res[i][j-1]+1)
        for i in range(r-1,-1,-1):
            for j in range(c-1,-1,-1):
                if i<r-1:
                    res[i][j] = min(res[i][j], res[i+1][j]+1)
                if j <c-1:
                    res[i][j] = min(res[i][j], res[i][j+1]+1)
                   
        return res