Leetcode 542. 01 Matrix (Python)

Related Topic

Breadth-First-Search.

Description

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.

Sample I/O

Example 1

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

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

Example 2

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

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

Note

1. The number of elements of the given matrix will not exceed 10,000.
2. There are at least one 0 in the given matrix.
3. The cells are adjacent in only four directions: up, down, left and right.

Methodology

Start from each 0, find the distance between this 0 and each no-zero element. update the distance if the distance is shorter than the current.

Code(BFS)

def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
        q = collections.deque()
        row = len(matrix)
        col = len(matrix[0])
        dirs = [(-1, 0),(0, -1),(1,0),(0,1)] 
        for x in range(row):
            for y in range(col):
                if matrix[x][y] == 0:
                    q.append((x,y))
                else:
                    matrix[x][y] = float("inf")
        while q:
            x,y = q.popleft()
            for dx, dy in dirs:
                new_x, new_y = x+dx, y+dy
                if 0 <= new_x < row and 0 <= new_y < col and matrix[new_x][new_y] > matrix[x][y]+1:
                    q.append((new_x,new_y))
                    matrix[new_x][new_y] = matrix[x][y]+1
        return matrix

BigO

We traversal all elements of the list twice so time complexity is O(2mn) where m is size of matrix and n is size of the columns