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 cell, you've found its shortest path to any .
Time: since each cell is visited once. Space: for the result matrix and queue.