01 Matrix
MediumMulti-source BFS from every zero at once
Problem
Given a binary matrix, return a matrix of the distance of each cell to the nearest 0.
BFS outward from all zeros at once; each wave labels the next ring with its distance.
The idea
Instead of searching outward from each 1, seed the queue with every 0 at distance 0 and expand once. Because all sources start together, the first time BFS reaches a cell it has come from the nearest zero, so one pass answers every cell in O(rows x cols).
The trick
- Push all the zeros before starting — that is what makes it multi-source.
- First visit is the shortest distance; never update a cell twice.
- Per-cell BFS would be O((rc)²); this is O(rc).
Step 1 of 6. Every rotten orange (R) rots its fresh (F) neighbours each minute — a multi-source BFS. minute 0, fresh 6.
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.