01 Matrix

BFS

Problem

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Thought Process

• BFS

• Store 0's in the queue so we can look at their neighbors

Solution

Using visited set

from collections import deque
class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        
        q = deque()
        visited = set()
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    q.append([i,j])
                    visited.add((i,j))
                    
        d = [[1,0], [-1, 0], [0,1], [0,-1]]     
        while q: 
            node = q.popleft()
            x = node[0]
            y = node[1]
            for i in d:
                newX = x+i[0]
                newY = y+i[1]
                
                    
                if newX < 0 or newX >= len(matrix) or newY >= len(matrix[0]) or newY < 0 or (newX, newY) in visited:
                    continue
                
                matrix[newX][newY] = matrix[x][y]+1 
               
                q.append([newX, newY])
                visited.add((newX, newY))
                
                        
        return matrix
                
            

Not using visited set

from collections import deque
class Solution:
    def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        
        q = deque()
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    q.append([i,j])
                else:
                    matrix[i][j] = float('inf')
                    
        d = [[1,0], [-1, 0], [0,1], [0,-1]]     
        while q: 
            node = q.popleft()
            x = node[0]
            y = node[1]
            for i in d:
                newX = x+i[0]
                newY = y+i[1]
                
                    
                if newX < 0 or newX >= len(matrix) or newY >= len(matrix[0]) or newY < 0 or matrix[newX][newY] <= matrix[x][y]+1:
                    continue
                
                matrix[newX][newY] = matrix[x][y]+1 
               
                q.append([newX, newY])
                
                        
        return matrix
                
            

• Notice here we don't care about the "deepest level" or using levels in anyways (like in Rotting Oranges or As Far Land As Possible). This is why we don't utilize the levels in this BFS problem

Time Complexity

• Time: O(n*n)

• Space: O(n*n) since we are storing all the 0's and 1's in the queue