LeetCode Solutions Blog

01 Matrix

Number: 542

Difficulty: Medium

Paid? No

Problem Description

Given an m x n binary matrix mat, the goal is to return a matrix where each cell contains the distance from that cell to its nearest 0. The distance is measured in steps, moving only up, down, left, or right.

Key Insights

Treat all 0s as starting points for a multi-source BFS.
Update each neighboring cell's distance if a shorter distance is found.
Utilize a queue to process cells in order of increasing distance.
Ensure that each cell is processed only once by marking visited cells.

Space and Time Complexity

Time Complexity: O(mn) since each cell is processed once. Space Complexity: O(mn) for the queue and the answer matrix.

Solution

We use a multi-source Breadth-First Search (BFS) where every 0 in the matrix is initially added to the BFS queue. Each neighboring cell that is a 1 will have its distance updated to be one plus the distance of the current cell if it hasn’t been visited yet (or if a smaller distance is found). This ensures that the first time a 1 is reached, it is reached by the shortest path. Data structures used include a queue (or deque) for BFS and the matrix itself for storing distances.

Code Solutions

from collections import deque

def updateMatrix(mat):
    # Get the dimensions of the matrix
    rows, cols = len(mat), len(mat[0])
    # Initialize a queue for multi-source BFS
    queue = deque()
    
    # Initialize the matrix: use -1 to indicate unvisited cells
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                # Enqueue all 0 cells as starting points
                queue.append((r, c))
            else:
                # Mark 1 cells as unvisited (or infinite distance)
                mat[r][c] = -1
                
    # Directions for neighbors (up, down, left, right)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    # BFS traversal to update distances
    while queue:
        r, c = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            # Check boundaries and if neighbor has not been visited
            if 0 <= nr < rows and 0 <= nc < cols and mat[nr][nc] == -1:
                # Update neighbor's distance
                mat[nr][nc] = mat[r][c] + 1
                # Enqueue the neighbor for further BFS processing
                queue.append((nr, nc))
                
    return mat

# Example usage:
# print(updateMatrix([[0,0,0],[0,1,0],[1,1,1]]))