Run it in your head. What does this return?

[[0, 0, 0], [0, 1, 0], [1, 2, 1]]

[[1, 0, 0], [0, 1, 0], [1, 2, 1]]

[[0, 0, 0], [0, 1, 0], [0, 0, 0]]

HomeGraphs

Distance of nearest cell having one

Medium

Multi-source BFS from every 1

Problem

For each cell in a binary grid, return its distance to the nearest cell containing 1.

In simple words

BFS outward from all the 1-cells at once, labelling each cell with its distance.

The idea

Seed the queue with every cell containing a 1 at distance 0 and expand once. Because all sources start together, the first time BFS reaches a cell it has arrived from the nearest 1.

The trick

First visit is the shortest distance — never update a cell twice.
One pass answers every cell: O(rows × cols).

←→stepspaceplay

minute0

fresh6

1/6

Optimal

timeO(rows·cols)spaceO(rows·cols)

All sources start at minute 0.

1// enqueue all rotten cells; BFS by layers,2// converting fresh neighbors, counting minutes.3while (q.length && fresh > 0) {4  minutes++;5  for (let n = q.length; n > 0; n--) spread(q.shift());6}7return fresh === 0 ? minutes : -1;

Input

grid: 3 × 3

Memory

minute: 0
fresh: 6

Output

minute: 0
fresh: 6
answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output:: [[0, 0, 0], [0, 1, 0], [1, 2, 1]]
Explanation:: Each cell's distance to the nearest 0.

Example 2

Input:: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output:: [[0, 0, 0], [0, 1, 0], [0, 0, 0]]
Explanation:: The single 1 is one step from a 0.

Example 3

Input:: mat = [[0]]
Output:: [[0]]
Explanation:: A zero is distance 0.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.