0542_01_Matrix.md

Leetcode 0542. 01 Matrix

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

Solution

class Solution:
    def updateMatrix(self, matrix):
        m, n = len(matrix), len(matrix[0])
        dist = [[float('inf')]*n for _ in range(m)]
        dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        
        def bfs(r, c):
            queue = [(r, c)]
            while queue:
                x, y = queue.pop(0)
                for dx, dy in dirs:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and dist[nx][ny] > dist[x][y] + 1:
                        dist[nx][ny] = dist[x][y] + 1
                        queue.append((nx, ny))
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    dist[i][j] = 0
                    bfs(i, j)
        return dist

Step-by-step Explanation:

1. Initialize a 2D array dist to store the distance of the nearest 0 for each cell, initially set to infinity.
2. Define a BFS function to update the distance for each cell.
3. For each cell in the matrix, if it's a 0, set its distance to 0 and run the BFS function to update the distances for its neighbors.
4. Finally, return the dist array.

Complexity Analysis:

• Time complexity: O(m*n), where m is the number of rows and n is the number of columns in the matrix, because in the worst case we need to visit all cells.
• Space complexity: O(m*n), because we need to store the distance for all cells.