LeetCode 542 - 01 Matrix

This problem gives us an m x n binary matrix where every cell contains either 0 or 1. For every cell in the matrix, we must compute the distance to the nearest cell containing 0. Distance is measured using Manhattan movement with four directions only: up, down, left, and right.

leetcodemediumarraydynamic-programmingbreadth-first-searchmatrix

LeetCode Problem 542

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Breadth-First Search, Matrix

Solution

Problem Understanding

This problem gives us an m x n binary matrix where every cell contains either 0 or 1. For every cell in the matrix, we must compute the distance to the nearest cell containing 0.

Distance is measured using Manhattan movement with four directions only: up, down, left, and right. Moving from one cell to an adjacent cell costs 1.

If a cell already contains 0, then its answer is naturally 0 because the nearest zero is the cell itself. For cells containing 1, we must determine how many moves are required to reach the closest zero.

For example, consider this matrix:

0 0 0
0 1 0
0 0 0

The center cell contains 1, and it is adjacent to a zero, so its distance is 1.

The constraints are important:

  • 1 <= m * n <= 10^4
  • Each cell is either 0 or 1
  • There is at least one 0

The total number of cells is at most 10^4, which means we should aim for an algorithm close to linear time, O(m * n). An inefficient repeated search from every cell could become too slow.

A few important edge cases stand out immediately:

  • A matrix containing only zeros, every answer should remain zero.
  • A matrix where many ones are far from the nearest zero.
  • A single row or single column matrix.
  • Large connected regions of ones where naive repeated searches would revisit the same cells many times.
  • The problem guarantees at least one zero exists, so every cell will always have a valid answer.

Approaches

Brute Force Approach

The most straightforward idea is to process every cell independently.

For each cell containing 1, we could run a Breadth-First Search outward until we encounter a 0. Since BFS explores level by level, the first zero found gives the shortest distance.

This works correctly because BFS guarantees the shortest path in an unweighted grid.

However, this approach is very inefficient because we repeat nearly identical searches for many cells. If the matrix contains mostly ones, each BFS may explore a large portion of the matrix again and again.

Suppose there are m * n cells, and each BFS may visit up to m * n cells. The total complexity becomes:

O((m * n)^2)

That is too slow for the constraint limit.

Optimal Approach, Multi-Source BFS

The key insight is that instead of starting a BFS from every 1, we can reverse the perspective.

We already know the distance for every zero cell:

distance = 0

So rather than searching from ones toward zeros, we can start simultaneously from all zero cells and spread outward.

This is called multi-source BFS.

The BFS frontier expands level by level from every zero at the same time. The first time a 1 cell is reached must be through the shortest possible path to a zero.

This works because BFS explores in increasing order of distance.

The algorithm becomes very efficient because every cell is processed at most once.

Approach Time Complexity Space Complexity Notes
Brute Force O((m * n)^2) O(m * n) Run BFS separately from every cell
Optimal O(m * n) O(m * n) Multi-source BFS starting from all zeros

Algorithm Walkthrough

  1. Create a result matrix to store distances.

We initialize all cells with a large value such as infinity, except cells containing 0. 2. Push all zero cells into a queue.

Every zero cell becomes a BFS starting point because their distance is already known to be 0. 3. Begin BFS processing.

While the queue is not empty:

  • Remove the front cell.
  • Check its four neighboring cells.
  • If visiting a neighbor through the current cell produces a smaller distance, update it and push that neighbor into the queue.
  1. Expand level by level.

BFS naturally processes cells in increasing order of distance. This guarantees that when we first assign a distance to a cell, it is the shortest possible distance to a zero. 5. Continue until the queue is empty.

Once BFS finishes, every cell contains the minimum distance to the nearest zero.

Why it works

BFS explores nodes in order of shortest path length in an unweighted graph. The matrix can be viewed as a graph where each cell connects to its four neighbors.

Since all zero cells are inserted into the queue initially with distance 0, the BFS wave expands outward simultaneously from every zero. The first time a cell is reached must therefore correspond to the shortest possible path from any zero.

Because each update only occurs when a shorter distance is found, the final matrix contains correct minimum distances.

Python Solution

from collections import deque
from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        rows = len(mat)
        cols = len(mat[0])

        distances = [[float("inf")] * cols for _ in range(rows)]
        queue = deque()

        # Initialize all zero cells
        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    distances[r][c] = 0
                    queue.append((r, c))

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

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

                if (
                    0 <= new_row < rows
                    and 0 <= new_col < cols
                    and distances[new_row][new_col] > distances[row][col] + 1
                ):
                    distances[new_row][new_col] = distances[row][col] + 1
                    queue.append((new_row, new_col))

        return distances

The implementation begins by creating a distance matrix initialized with infinity. This represents cells whose shortest distance has not yet been discovered.

Next, every zero cell is inserted into the BFS queue and assigned distance 0. These cells act as simultaneous BFS starting points.

The directions array simplifies neighbor traversal by encoding the four possible movements.

The BFS loop repeatedly removes cells from the queue and examines their neighbors. If a neighbor can be reached with a shorter distance than previously recorded, the distance is updated and the neighbor is added to the queue.

Because BFS processes cells in increasing distance order, each update propagates the correct shortest distance outward from the nearest zero.

Finally, the completed distance matrix is returned.

Go Solution

func updateMatrix(mat [][]int) [][]int {
	rows := len(mat)
	cols := len(mat[0])

	distances := make([][]int, rows)

	for r := 0; r < rows; r++ {
		distances[r] = make([]int, cols)

		for c := 0; c < cols; c++ {
			distances[r][c] = 1 << 30
		}
	}

	type Cell struct {
		row int
		col int
	}

	queue := []Cell{}

	// Initialize all zero cells
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if mat[r][c] == 0 {
				distances[r][c] = 0
				queue = append(queue, Cell{r, c})
			}
		}
	}

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	front := 0

	// Multi-source BFS
	for front < len(queue) {
		current := queue[front]
		front++

		for _, dir := range directions {
			newRow := current.row + dir[0]
			newCol := current.col + dir[1]

			if newRow >= 0 &&
				newRow < rows &&
				newCol >= 0 &&
				newCol < cols &&
				distances[newRow][newCol] > distances[current.row][current.col]+1 {

				distances[newRow][newCol] =
					distances[current.row][current.col] + 1

				queue = append(queue, Cell{newRow, newCol})
			}
		}
	}

	return distances
}

The Go implementation follows the same logic as the Python solution, but there are a few language-specific details worth noting.

Go does not provide a built-in deque structure, so the queue is implemented using a slice and a front index. This avoids expensive slice shifting operations.

Instead of using infinity, the solution initializes distances with a very large integer value using 1 << 30.

A small Cell struct improves readability when storing row and column coordinates in the queue.

Worked Examples

Example 1

Input:

0 0 0
0 1 0
0 0 0

Initial state:

Cell Distance
All zeros 0
Center 1 inf

Initial queue:

[(0,0), (0,1), (0,2), (1,0), (1,2), (2,0), (2,1), (2,2)]

Processing begins.

When processing (0,1):

  • Neighbor (1,1) gets distance 1

Updated matrix:

0 0 0
0 1 0
0 0 0

No further updates improve the center cell.

Final answer:

0 0 0
0 1 0
0 0 0

Example 2

Input:

0 0 0
0 1 0
1 1 1

Initial distances:

0 0 0
0 inf 0
inf inf inf

Initial queue:

[(0,0), (0,1), (0,2), (1,0), (1,2)]

Processing (0,1):

  • (1,1) becomes 1

Matrix:

0 0 0
0 1 0
inf inf inf

Processing (1,0):

  • (2,0) becomes 1

Matrix:

0 0 0
0 1 0
1 inf inf

Processing (1,1):

  • (2,1) becomes 2

Matrix:

0 0 0
0 1 0
1 2 inf

Processing (1,2):

  • (2,2) becomes 1

Final matrix:

0 0 0
0 1 0
1 2 1

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Every cell enters the queue at most once
Space O(m * n) Distance matrix and BFS queue may store all cells

The algorithm is linear in the number of cells. Each cell is processed once during BFS, and each edge between neighboring cells is examined a constant number of times.

The auxiliary space comes from the distance matrix and the BFS queue. In the worst case, the queue may contain nearly all cells simultaneously.

Test Cases

from typing import List

class Solution:
    def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]:
        from collections import deque

        rows = len(mat)
        cols = len(mat[0])

        distances = [[float("inf")] * cols for _ in range(rows)]
        queue = deque()

        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    distances[r][c] = 0
                    queue.append((r, c))

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

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

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and distances[nr][nc] > distances[row][col] + 1
                ):
                    distances[nr][nc] = distances[row][col] + 1
                    queue.append((nr, nc))

        return distances

solution = Solution()

# Example 1
assert solution.updateMatrix([
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]) == [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
]  # center cell adjacent to zero

# Example 2
assert solution.updateMatrix([
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
]) == [
    [0, 0, 0],
    [0, 1, 0],
    [1, 2, 1]
]  # bottom middle requires two steps

# Single cell zero
assert solution.updateMatrix([
    [0]
]) == [
    [0]
]  # smallest valid matrix

# Single row
assert solution.updateMatrix([
    [0, 1, 1, 1]
]) == [
    [0, 1, 2, 3]
]  # horizontal propagation

# Single column
assert solution.updateMatrix([
    [0],
    [1],
    [1]
]) == [
    [0],
    [1],
    [2]
]  # vertical propagation

# Multiple zero sources
assert solution.updateMatrix([
    [0, 1, 1],
    [1, 1, 1],
    [1, 1, 0]
]) == [
    [0, 1, 2],
    [1, 2, 1],
    [2, 1, 0]
]  # shortest path may come from different zeros

# All zeros
assert solution.updateMatrix([
    [0, 0],
    [0, 0]
]) == [
    [0, 0],
    [0, 0]
]  # no updates required

# Larger connected ones region
assert solution.updateMatrix([
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1]
]) == [
    [2, 1, 2],
    [1, 0, 1],
    [2, 1, 2]
]  # distances radiate outward
Test Why
[[0,0,0],[0,1,0],[0,0,0]] Validates simple adjacent distances
[[0,0,0],[0,1,0],[1,1,1]] Tests propagation over multiple layers
[[0]] Smallest valid input
Single row matrix Ensures horizontal traversal works
Single column matrix Ensures vertical traversal works
Multiple zeros Confirms nearest source is selected
All zeros Verifies no unnecessary updates
Large ones region Tests BFS wave expansion correctness

Edge Cases

One important edge case is a matrix containing only zeros. A buggy implementation might still attempt BFS updates unnecessarily or accidentally overwrite valid distances. In this solution, every zero is initialized with distance 0, and no neighbor update can improve those values, so the matrix remains unchanged.

Another important case is a single row or single column matrix. Some implementations incorrectly assume both dimensions are larger than one, causing index errors during neighbor traversal. This solution carefully checks bounds before accessing neighbors, so narrow matrices work correctly.

A third critical edge case is when multiple zeros exist and a cell could be reached from different directions. A naive DFS approach might incorrectly record a longer path first and never improve it later. Multi-source BFS avoids this issue because cells are explored in increasing order of distance, guaranteeing the first valid distance discovered is optimal.

A final subtle case occurs when large connected regions of ones exist far from any zero. Repeated independent searches would become extremely inefficient. The multi-source BFS solution handles this efficiently because every cell is processed only once regardless of how many paths could reach it.