542. 01 Matrix (Medium)

Problem

Given an m x n binary matrix mat, return a matrix of the same size where each cell contains the distance to the nearest 0. Distance is measured as the number of steps (4-directional, no diagonals).

Example

mat = [[0,0,0],[0,1,0],[0,0,0]] → [[0,0,0],[0,1,0],[0,0,0]]
mat = [[0,0,0],[0,1,0],[1,1,1]] → [[0,0,0],[0,1,0],[1,2,1]]

LeetCode 542 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach: Multi-source BFS from all zeros simultaneously

The key insight is to seed the BFS queue with every 0 cell at distance 0, then expand outward. Because BFS explores by distance levels, the first time a 1 cell is reached it has the shortest possible distance to any 0. Running a separate BFS from each 0 would be $O((m*n)$ ^2) in the worst case; seeding all zeros at once keeps it $O(m*n)$ .

from collections import deque

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])                     # L1: grid dimensions
    dist = [[float('inf')] * cols for _ in range(rows)]   # L2: O(m*n) distance matrix
    q = deque()

    for r in range(rows):                                  # L3: seed queue with all 0-cells
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0                             # L4: O(1) distance for 0-cells
                q.append((r, c))                           # L5: O(1) enqueue

    while q:                                               # L6: BFS main loop
        r, c = q.popleft()                                 # L7: O(1) dequeue
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == float('inf'):
                dist[nr][nc] = dist[r][c] + 1             # L8: O(1) update distance
                q.append((nr, nc))                         # L9: O(1) enqueue neighbor

    return dist                                            # L10: O(1)

function updateMatrix(mat: number[][]): number[][] {
    const rows = mat.length, cols = mat[0].length;                    // L1: grid dimensions
    const dist: number[][] = Array.from({ length: rows },
        () => new Array(cols).fill(Infinity));                        // L2: O(m*n) distance matrix
    const q: [number, number][] = [];

    for (let r = 0; r < rows; r++) {                                  // L3: seed queue with all 0-cells
        for (let c = 0; c < cols; c++) {
            if (mat[r][c] === 0) {
                dist[r][c] = 0;                                       // L4: O(1) distance for 0-cells
                q.push([r, c]);                                       // L5: O(1) enqueue
            }
        }
    }

    let head = 0;
    while (head < q.length) {                                         // L6: BFS main loop
        const [r, c] = q[head++];                                     // L7: O(1) dequeue
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] === Infinity) {
                dist[nr][nc] = dist[r][c] + 1;                        // L8: O(1) update distance
                q.push([nr, nc]);                                     // L9: O(1) enqueue neighbor
            }
        }
    }

    return dist;                                                      // L10: O(1)
}

final class Solution {
    func updateMatrix(_ mat: [[Int]]) -> [[Int]] {
        let rows = mat.count, cols = mat[0].count
        var distance = Array(repeating: Array(repeating: -1, count: cols), count: rows)
        var queue: [(Int, Int)] = [], head = 0
        for row in 0..<rows { for col in 0..<cols where mat[row][col] == 0 { distance[row][col] = 0; queue.append((row, col)) } }
        while head < queue.count {
            let (row, col) = queue[head]; head += 1
            for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
                let nr = row + dr, nc = col + dc
                if nr >= 0 && nr < rows && nc >= 0 && nc < cols && distance[nr][nc] == -1 {
                    distance[nr][nc] = distance[row][col] + 1; queue.append((nr, nc))
                }
            }
        }
        return distance
    }
}

Where the time goes, line by line

Variables: m = grid rows, n = grid cols.

Line	Per-call cost	Times executed	Contribution
L2 (init dist)	$O(1)$ per cell	m * n	$O(m * n)$
L3 (seed scan)	$O(1)$ per cell	m * n	$O(m * n)$
L5 (enqueue 0-cells)	$O(1)$	up to m * n	$O(m * n)$
L7 (dequeue)	$O(1)$	once per cell	*$O(m n)$ ← dominates**
L8 (update dist)	$O(1)$	once per 1-cell	$O(m * n)$
L9 (enqueue)	$O(1)$	once per 1-cell	*$O(m n)$ ← dominates**

Each cell enters the queue at most once (the dist == inf guard in the neighbor check prevents re-enqueueing). The seed scan in L3 and the BFS body in L6 together visit every cell a constant number of times.

Complexity

Time: $O(m * n)$ , driven by L7/L9 (each cell enqueued and dequeued at most once).
Space: $O(m * n)$ for the distance matrix (L2) and worst-case queue size.

Why multi-source BFS works

Treat all 0 cells as a single virtual source at distance 0. BFS explores in shells: all cells at distance 1 before distance 2, etc. The first time any 1 cell is dequeued, its recorded distance is the true shortest path to the nearest 0. This is the same principle as Rotting Oranges (994) and Walls and Gates (286).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space	Notes
BFS from each 0 separately	$O((m * n)$ ^2)	$O(m * n)$	Too slow
Multi-source BFS	*$O(m n)$**	*$O(m n)$**	Canonical

from collections import deque

def update_matrix(mat):
    rows, cols = len(mat), len(mat[0])
    dist = [[float('inf')] * cols for _ in range(rows)]
    q = deque()
    for r in range(rows):
        for c in range(cols):
            if mat[r][c] == 0:
                dist[r][c] = 0
                q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and dist[nr][nc] == float('inf'):
                dist[nr][nc] = dist[r][c] + 1
                q.append((nr, nc))
    return dist

def _run_tests():
    # Example 1: center 1-cell is distance 1 from any neighbor
    assert update_matrix([[0,0,0],[0,1,0],[0,0,0]]) == [[0,0,0],[0,1,0],[0,0,0]]

    # Example 2: bottom row has no 0, distances computed correctly
    assert update_matrix([[0,0,0],[0,1,0],[1,1,1]]) == [[0,0,0],[0,1,0],[1,2,1]]

    # Edge: all zeros
    assert update_matrix([[0,0],[0,0]]) == [[0,0],[0,0]]

    # Edge: single zero
    assert update_matrix([[0]]) == [[0]]

    # Edge: single one surrounded by zeros
    assert update_matrix([[0,0,0],[0,0,0],[0,0,1]]) == [[0,0,0],[0,0,0],[0,0,1]]

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function updateMatrix(mat: number[][]): number[][] {
    const rows = mat.length, cols = mat[0].length;
    const dist: number[][] = Array.from({ length: rows }, () => new Array(cols).fill(Infinity));
    const q: [number, number][] = [];
    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++)
            if (mat[r][c] === 0) { dist[r][c] = 0; q.push([r, c]); }
    let head = 0;
    while (head < q.length) {
        const [r, c] = q[head++];
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && dist[nr][nc] === Infinity) {
                dist[nr][nc] = dist[r][c] + 1;
                q.push([nr, nc]);
            }
        }
    }
    return dist;
}

console.assert(JSON.stringify(updateMatrix([[0,0,0],[0,1,0],[0,0,0]])) === JSON.stringify([[0,0,0],[0,1,0],[0,0,0]]));
console.assert(JSON.stringify(updateMatrix([[0,0,0],[0,1,0],[1,1,1]])) === JSON.stringify([[0,0,0],[0,1,0],[1,2,1]]));
console.assert(JSON.stringify(updateMatrix([[0,0],[0,0]])) === JSON.stringify([[0,0],[0,0]]));
console.assert(JSON.stringify(updateMatrix([[0]])) === JSON.stringify([[0]]));
console.log("all tests pass");

Number of Islands, same BFS-on-grid template
Shortest Path in Binary Matrix, BFS shortest path through 0-cells
Rotting Oranges, multi-source BFS spreading pattern

Grid DP, the row and column state pattern for matrix paths and local moves.
BFS, the level order frontier pattern for shortest unweighted distance and wave expansion.

542. 01 Matrix (Medium)

Problem

Try it yourself

Approach: Multi-source BFS from all zeros simultaneously

Why multi-source BFS works

Summary

Test cases

Related topics

Related concepts