We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

01 Matrix

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem involves finding the shortest distance from each cell to the nearest cell containing a 0.
  • A breadth-first search (BFS) is an effective way to explore all possible paths and find the shortest distances from multiple sources (the 0s).
  • Using a queue data structure allows us to efficiently process cells layer by layer, updating distances as we progress.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n)

Solution

To solve this problem, we utilize the Breadth-First Search (BFS) algorithm. The idea is to treat all the cells containing 0 as starting points and explore their neighboring cells to calculate the distance to the nearest 0 for each cell in the matrix. A queue is used to facilitate the BFS traversal, while a distance matrix keeps track of the distances from each cell to the nearest 0.

  1. Initialize a distance matrix with a large value for each cell.
  2. Use a queue to store the coordinates of all cells containing 0 and set their distance to 0 in the distance matrix.
  3. For each cell processed from the queue, check its four possible neighbors (up, down, left, right).
  4. If a neighbor has not been visited (i.e., its distance is still large), update its distance and add it to the queue.
  5. Continue this process until all reachable cells have been processed.

Code Solutions

from collections import deque

def updateMatrix(mat):
    if not mat:
        return []
    
    rows, cols = len(mat), len(mat[0])
    distance = [[float('inf')] * cols for _ in range(rows)]
    queue = deque()

    # Initialize the queue with all the 0's positions
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                distance[r][c] = 0
                queue.append((r, c))

    # Directions for moving in the matrix
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    while queue:
        r, c = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if distance[nr][nc] > distance[r][c] + 1:
                    distance[nr][nc] = distance[r][c] + 1
                    queue.append((nr, nc))
    
    return distance
← Back to All Questions