Domain 2MediumCORE

01 Matrix

We are given a binary matrix containing only 0s and 1s. The goal is to transform this grid such that every cell contains an integer representing its Manhattan distance to the nearest '0'. - Input: A list of lists (2D array) with dimensions $R times C$. Elements are integers {0, 1}. - Output: Same dimensional matrix where each element holds a non-negative integer. - Constraints: Grid size up to 10,000 elements ($N$). At least one '0' exists. Adjacency is strictly orthogonal (up/down/left/right).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Breadth-first Search

542. 01 Matrix

Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 41.1%


Problem Breakdown

We are given a binary matrix containing only 0s and 1s. The goal is to transform this grid such that every cell contains an integer representing its Manhattan distance to the nearest ‘0’.

  • Input: A list of lists (2D array) with dimensions R×CR \times C. Elements are integers {0, 1}.
  • Output: Same dimensional matrix where each element holds a non-negative integer.
  • Constraints: Grid size up to 10,000 elements (NN). At least one ‘0’ exists. Adjacency is strictly orthogonal (up/down/left/right).

Implicitly, this models an unweighted graph problem on a grid where we want the shortest path distance from any source node (‘0’) to every other reachable node. Since edge weights are uniform (1), Breadth-First Search (BFS) guarantees finding the shortest path first.

Intuition

A naive approach might be: for each ‘1’ cell, run a BFS/DFS until we hit a ‘0’. However, if there are many ‘1’s and few ‘0’s, this is inefficient (O((R⋅C)2)O((R \cdot C)^2) worst case). Even better, running a search from each ‘0’ to fill the grid would be O(K⋅R⋅C)O(K \cdot R \cdot C) where KK is the count of zeros. If there are many zeros (e.g., half the matrix), this degrades significantly.

The key insight here is Multi-Source BFS. Instead of searching from every cell individually, we treat all ‘0’s as starting points simultaneously at time step 0. We initialize a queue with coordinates of all existing ‘0’ cells and set their distance to 0. As the BFS expands layer by layer (wavefront propagation), any unvisited neighbor encountered for the first time is guaranteed to be reached via the shortest path from some nearest zero. This ensures we fill distances correctly in O(R⋅C)O(R \cdot C) because each cell is processed exactly once.

Approach

  1. Initialization: Create a result matrix initialized with -1 (representing unvisited). Iterate through the input grid; if a cell contains ‘0’, set its distance to 0 and add it to our BFS queue immediately. If it’s a ‘1’, leave as -1 for now.
  2. BFS Execution: While the queue is not empty:
    • Dequeue current coordinates (r, c).
    • Explore all four valid neighbors (up, down, left, right).
    • If a neighbor is within bounds and has value -1 (unvisited):
      • Update its distance to current_distance + 1 in the result matrix.
      • Enqueue that neighbor for further exploration.
  3. Termination: The queue empties once all reachable cells have been visited. Since every cell is connected via valid paths and at least one ‘0’ exists, we will visit every cell exactly once. Return the distance matrix.

Complexity Analysis

  • Time Complexity: O(R⋅C)O(R \cdot C). We iterate through each cell a constant number of times (once during initialization to build queue, once when processing neighbors). Each edge is visited at most twice in BFS logic. With 10,000 elements total, this fits well within time limits.
  • Space Complexity: O(R⋅C)O(R \cdot C). We store the result matrix and a deque that can hold up to all cells (worst case: ring of zeros surrounding ones).

Solution

from collections import deque
from typing import List

def updateMatrix(matrix: List[List[int]]) -> List[List[int]]:
    if not matrix or not matrix[0]:
        return []
    
    rows, cols = len(matrix), len(matrix[0])
    # Initialize distance grid with -1 (unvisited)
    dist = [[-1] * cols for _ in range(rows)]
    queue = deque()
    
    # Step 1: Add all '0's to the queue and initialize their distances
    for r in range(rows):
        for c in range(cols):
            if matrix[r][c] == 0:
                dist[r][c] = 0
                queue.append((r, c))
    
    # Directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    # Step 2: Multi-source BFS
    while queue:
        r, c = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            # Check bounds and if cell is unvisited (-1)
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == -1:
                dist[nr][nc] = dist[r][c] + 1
                queue.append((nr, nc))
                
    return dist

# Example usage (uncomment to test locally)
# print(updateMatrix([[0,0,0],[0,1,0],[0,0,0]])) 

Edge Cases Handled

  • All Zeros: The queue is initialized with all cells. Loop runs once per cell; distances remain 0. Correctly returns matrix of zeros.
  • Single Cell Matrix: If [0], loop sets dist to 0, returns [[0]]. If [1] (invalid by constraints), but if it were possible and no ‘0’ existed, queue would be empty initially; however, problem guarantees at least one ‘0’.
  • ‘0’s on Boundary: BFS handles boundary checks (if 0 <= nr < rows...) correctly so neighbors outside grid are ignored.
  • Large Grid (10k elements): Since complexity is linear relative to cell count and Python deque operations are O(1)O(1), this scales efficiently within the given constraints without hitting recursion limits or memory overheads typical of DFS on large grids.