Here's the solution:
function updateMatrix(mat):
rows := number of rows in mat
cols := number of columns in mat
result := 2D array of size rows x cols, initialized to -1
queue := empty queue
directions := [(0,1), (1,0), (0,-1), (-1,0)]
for r from 0 to rows - 1:
for c from 0 to cols - 1:
if mat[r][c] = 0 then
result[r][c] := 0
push (r, c) to queue
while queue is not empty:
(r, c) := pop from queue
for each (dr, dc) in directions:
nr := r + dr
nc := c + dc
if nr, nc is in bounds and result[nr][nc] = -1 then
result[nr][nc] := result[r][c] + 1
push (nr, nc) to queue
return result
Time: because each cell is visited once. Space: for the result matrix and queue.