LeetCode 542 01 Matrix - Algorithm

Here's the algorithm:

function updateMatrix(mat):
    rows = mat.rows
    cols = mat.cols
    result = matrix of -1 with size rows x cols
    queue = empty

    // Step 1: Push all 0 cells
    for r from 0 to rows - 1:
        for c from 0 to cols - 1:
            if mat[r][c] == 0:
                result[r][c] = 0
                queue.push((r, c))

    // Step 2: Multi-source BFS
    while queue is not empty:
        (r, c) = queue.pop_front()
        for each neighbor (nr, nc) of (r, c):
            if in_bounds(nr, nc) and result[nr][nc] == -1:
                result[nr][nc] = result[r][c] + 1
                queue.push((nr, nc))

    return result

The core idea: BFS visits cells in order of increasing distance. The first time you reach a $1$ cell, you've found its shortest path to any $0$.

Time: $O(m \times n)$ since each cell is visited once. Space: $O(m \times n)$ for the result matrix and queue.