01 Matrix medium

Problem Statement

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

The distance between two cells (r1, c1) and (r2, c2) is |r1 - r2| + |c1 - c2|.

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,1,0],[1,1,1],[0,1,0]] Output: [[0,1,0],[1,2,1],[0,1,0]]

Steps

1. Initialization: Create a result matrix dist of the same size as mat, filled with infinity (a large value). For cells containing 0 in mat, set the corresponding value in dist to 0.

2. Multi-source BFS: Perform a Breadth-First Search (BFS) starting from all cells containing 0. Use a queue to store the coordinates of cells to visit. Initially, add all (r,c) coordinates where mat[r][c] == 0 to the queue.

3. Iteration: While the queue is not empty:

   • Dequeue a cell (r,c).
   • Explore its four neighbors (up, down, left, right).
   • For each neighbor (nr, nc):
     • If dist[nr][nc] is still infinity (meaning it hasn't been visited), update dist[nr][nc] to dist[r,c] + 1 (distance from nearest 0) and enqueue (nr,nc).

4. Return: Return the dist matrix.

Explanation

The solution uses a multi-source Breadth-First Search (BFS) to efficiently find the shortest distance from each cell to the nearest 0. Starting from all 0s simultaneously, the BFS explores the matrix layer by layer, updating the distances in the dist matrix. This approach guarantees that the first time a cell is reached, it's reached by the shortest path from a 0. Using infinity as an initial value ensures that cells further away from zeros are correctly updated later.

Code

import collections

def updateMatrix(mat):
    """
    Finds the distance of the nearest 0 for each cell in a binary matrix.

    Args:
        mat: The input binary matrix (list of lists).

    Returns:
        The distance matrix (list of lists).
    """
    m, n = len(mat), len(mat[0])
    dist = [[float('inf')] * n for _ in range(m)]

    # Initialize distances for cells containing 0
    queue = collections.deque()
    for r in range(m):
        for c in range(n):
            if mat[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))

    # BFS
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and dist[nr][nc] == float('inf'):
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))

    return dist

Complexity

• Time Complexity: O(M*N), where M and N are the dimensions of the matrix. This is because each cell is visited and processed at most once during the BFS.
• Space Complexity: O(M*N) in the worst case, to store the dist matrix and the queue. In the best case the queue's size will be the number of zeros.