01 Matrix Nearest Zero

Compute Manhattan distance from each cell to the nearest 0 in a binary matrix.

matrix bfs distance queue

You are given a 2D list of integers `mat` where each element is either 0 or 1. Write a function `nearest_zero(mat)` that returns a new 2D list of the same dimensions, where the value at each position is the Manhattan distance to the nearest 0. Manhattan distance between two cells (r1, c1) and (r2, c2) is defined as |r1 - r2| + |c1 - c2|.

All cells with a 0 in the original matrix should have distance 0 in the result. You may assume that the matrix contains at least one 0. The function should not modify the input matrix.

Constraints

1 <= rows, cols <= 100. The input matrix contains only 0s and 1s and at least one 0. Time complexity should be O(rows * cols), space complexity O(rows * cols) for the output and auxiliary structures.

Example

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

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start a BFS from all 0 cells simultaneously.

Initialize the distance of all 1 cells to a large value (e.g., float('inf')).

Use a queue to propagate distances level by level; each cell's distance is its neighbor's distance + 1.

Edge: cells already 0 should have distance 0 and should not be updated again.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.