01 Matrix

542. 01 Matrix

GraphsBFSMediumLeetCode

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

The distance between two adjacent cells is 1.

Initial Grid

→

Final Grid (Distances)

Solution Explained

The problem asks for the distance of the nearest 0 for each cell in a binary matrix. This is a classic shortest path problem on an unweighted graph, which is a perfect use case for Breadth-First Search (BFS).

The core idea is to start a multi-source BFS from all cells containing 0 simultaneously. We can think of the 0s as the starting points of our search.

Algorithm Steps (BFS)

Initialize a distance matrix, marking 0s as distance 0 and others as unvisited (e.g., -1 or infinity).
Create a queue and add the coordinates of all cells containing 0.
While the queue is not empty, process cells level by level.
For each cell, explore its four neighbors.
If a neighbor is unvisited, update its distance and add it to the queue.

This process guarantees that we find the shortest path from a 0 to every other cell because BFS explores the grid layer by layer.

01 Matrix (BFS) Visualization

Progress1 / 1

Ready to start.

∞

Queue

Code Example


from collections import deque

class Solution:
    def updateMatrix(self, mat: list[list[int]]) -> list[list[int]]:
        m, n = len(mat), len(mat[0])
        queue = deque()
        
        # Initialize distances and queue with all 0s
        for r in range(m):
            for c in range(n):
                if mat[r][c] == 0:
                    queue.append((r, c))
                else:
                    mat[r][c] = -1 # Mark as unvisited
        
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        distance = 0
        
        while queue:
            level_size = len(queue)
            distance += 1
            for _ in range(level_size):
                r, c = queue.popleft()
                
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    
                    if 0 <= nr < m and 0 <= nc < n and mat[nr][nc] == -1:
                        mat[nr][nc] = distance
                        queue.append((nr, nc))
                        
        return mat