# Solving Leetcode Interviews in Seconds with AI: 01 Matrix


	# 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](https://www.chatmagic.app), 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
	```python
	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
	```