Introduction

In this blog post, we will explore how to solve the LeetCode problem "542" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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 sharing a common edge is 1. 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,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]] Constraints: m == mat.length n == mat[i].length 1 <= m, n <= 104 1 <= m * n <= 104 mat[i][j] is either 0 or 1. There is at least one 0 in mat. Note: This question is the same as 1765: https://leetcode.com/problems/map-of-highest-peak/

Explanation

Here's the solution to find the distance of the nearest 0 for each cell in a binary matrix:

• Breadth-First Search (BFS): Treat the matrix as a graph where adjacent cells are connected. Start BFS from all cells containing 0.

• Distance Tracking: During BFS, maintain the distance from the nearest 0 for each cell. The first time a cell is visited during BFS, its distance is determined.

• Optimized Traversal: To avoid cycles and redundant calculations, only visit unvisited cells or cells that can be reached with a shorter distance.

• Runtime & Storage Complexity: O(m n) runtime, O(m n) storage, where 'm' is the number of rows and 'n' is the number of columns in the matrix.

Code

    from collections import deque

def updateMatrix(mat: list[list[int]]) -> list[list[int]]:
    """
    Finds the distance of the nearest 0 for each cell in a binary matrix.

    Args:
        mat: The input binary matrix.

    Returns:
        A matrix with the distance of the nearest 0 for each cell.
    """

    m = len(mat)
    n = len(mat[0])
    dist = [[float('inf')] * n for _ in range(m)]
    queue = deque()

    # Add all 0s to the queue and set their distance to 0
    for i in range(m):
        for j in range(n):
            if mat[i][j] == 0:
                dist[i][j] = 0
                queue.append((i, j))

    # Define possible movements (up, down, left, right)
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    # BFS
    while queue:
        row, col = queue.popleft()

        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc

            if 0 <= new_row < m and 0 <= new_col < n and dist[new_row][new_col] == float('inf'):
                dist[new_row][new_col] = dist[row][col] + 1
                queue.append((new_row, new_col))

    return dist