Builds on Level-Order BFS, which you haven’t finished yet.
queue at the same time, so all sources spread together.Rotting Oranges (LC 994)(opens leetcode.com)
You're given an m x n grid whose cells each hold one of three values: 0 for an empty cell, 1 for a fresh orange, and 2 for a rotten one.
Each minute, rot spreads: any fresh orange touching a rotten orange along one of the four cardinal directions turns rotten too.
Work out how many minutes must pass before every orange is rotten, and return -1 if some fresh orange can never be reached.
Multi-Source BFS
all origin sources (t=0) ➔ concentric expansion ➔ shortest time| 1 | from collections import deque |
| 2 | from typing import Callable, Dict, Hashable, Iterable, List |
| 3 | |
| 4 | |
| 5 | def multi_source_bfs(sources: Iterable[Hashable], neighbors: Callable[[Hashable], Iterable[Hashable]]) -> Dict[Hashable, int]: |
| 6 | """Multi-Source BFS: the distance from every reachable cell to its nearest source. |
| 7 | Precondition: every move costs one step. |
| 8 | Every source starts at distance 0. neighbors(cell) yields the cells one step away that may be entered. |
| 9 | V = reachable cells. E = neighbour steps tried. T = the cost of one neighbors call. |
| 10 | Time: O(V * T + E) | Space: O(V) |
| 11 | """ |
| 12 | dist = {} # cell -> distance to its nearest source; doubles as the seen set |
| 13 | # 1. Seed Every Source at Distance 0: |
| 14 | # Placing every source in dist before the search starts lets them all spread |
| 15 | # together, instead of one source at a time. |
| 16 | for source in sources: |
| 17 | dist[source] = 0 |
| 18 | queue = deque(dist) # holds cells queued for this or a later ring, in enqueue order |
| 19 | |
| 20 | while queue: |
| 21 | # 2. Pop and Expand This Ring's Cell: |
| 22 | # Every move costs exactly 1 step, so the first time a cell is reached, it is |
| 23 | # reached by its nearest source, at the correct distance. |
| 24 | cell = queue.popleft() |
| 25 | for nxt in neighbors(cell): |
| 26 | if nxt not in dist: |
| 27 | # Marking a cell seen (giving it a dist entry) at enqueue time, not at |
| 28 | # pop time, stops it from being queued twice while still waiting. |
| 29 | dist[nxt] = dist[cell] + 1 |
| 30 | queue.append(nxt) |
| 31 | |
| 32 | return dist |
minutes rounds, queue holds exactly the oranges that turned rotten in round minutes, and fresh_count counts the fresh oranges not reached yet.Put every source into the queue at time 0, then run ordinary level-by-level BFS. All sources spread one ring per round, so each cell is reached first by its nearest source, and the round in which it turns is its distance to that source. The trap is the last round: count minutes only while fresh_count > 0, or the final round, which reaches nothing new, adds one minute too many.
See it run
Multi-Source BFS on grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]], step by step
minutes 0fresh_count 6len(queue) 1
The board is the grid. A cell holds 2 when rotten, 1 when fresh and 0 when empty. A row is one grid row.
sourcea cell that is 2 at minute 0popthe cell removed from queue nowrotsa fresh cell that becomes 2 in this stepqueueda cell waiting in queue
Every 2 goes into queue at minute 0: (0, 0). fresh_count = 6.
Gotcha 1 of 5
- The trap
Gotcha 1: Looping
while queuewithoutfresh_count > 0Mistakewhile queue:Fixwhile queue and fresh_count > 0:What happens: Each round adds one minute. The oranges that rot in the last useful round still go into
queue. Withwhile queue, the loop runs one more round for them. That round reaches no fresh orange, but it still adds one minute.Example: Rotting Oranges (LC 994): grid = [[2,1,1],[1,1,0],[0,1,1]]Mistake: returns 5Fix: returns 4
- There is one start cell and one target, as in Shortest Path in Binary Matrix (LC 1091), so nothing has to spread from many places at once. See Shortest-Path BFS
Deep Dive
Why starting from every source finds the nearest one
Level-Order BFS takes one start node, and round k handles the nodes at distance k from it. Multi-source BFS changes only the start. Put every source in queue before the first round. Then round k handles the cells at distance k from the nearest source.
Why the nearest source wins: every move costs one step, and the queue keeps its first in, first out order. A cell is added by the first neighbour that is popped and sees it as fresh. That neighbour is in the earliest possible round, so it is closest to some source. Any later source reaches the cell in a later round, and by then the cell is no longer fresh.
In Rotting Oranges (LC 994) with grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]], the only source is (0, 0). Round 1 rots (0, 1) and (1, 0). Round 2 rots (0, 2) and (1, 1). Round 3 rots (2, 1). Round 4 rots (2, 2). So minutes is 4.
Where minutes is counted, and the trap in the last round
minutes += 1 runs at the start of each round, before the cells of that round are popped. for _ in range(len(queue)) freezes the round size, as level_size does in Level-Order BFS. A cell that rots in this round is added behind the frozen cells, so it infects its neighbours in the next round.
Look at the last round of the example. In round 4, (2, 1) rots (2, 2), and fresh_count becomes 0. The queue still holds (2, 2). If the loop is while queue:, a fifth round starts. It pops (2, 2), finds no fresh neighbour, and still adds 1 to minutes. The result is 5 and not 4.
The loop while queue and fresh_count > 0 stops when nothing fresh is left. So minutes counts only the rounds that rotted at least one orange. If no orange is fresh at the start, fresh_count == 0 returns 0 before the loop.
Reachability, and the exact meaning of fresh_count
fresh_count is the number of fresh oranges that have not rotted yet. It goes down by 1 at the moment a cell is marked rotten and added to queue. Marking the cell at this moment stops a second neighbour from rotting it again in the same round.
When the queue empties and fresh_count is still above 0, some fresh orange had no path of fresh cells from any source. For grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]], the orange at (2, 0) has only empty neighbours, so the answer is -1. return minutes if fresh_count == 0 else -1 makes this case explicit. Without the check, the function returns 5, the number of rounds it ran, which is wrong.
Seeding every source matters. For grid = [[2, 1, 1], [1, 1, 1], [1, 1, 2]], seeding both rotten cells gives 2 minutes. Seeding only the first gives 3.
The cost, and when you need dist for every cell
Each cell is added at most once, and each pop tries 4 neighbours. For a grid with R rows and C columns, that is O(R * C) time. queue can hold O(R * C) cells, so the space is O(R * C). The card's template states O(V * T + E) for any graph.
Rotting Oranges (LC 994) needs one number, the time until the last orange rots, so a minutes counter is enough. Walls and Gates (LC 286), 01 Matrix (LC 542) and Map of Highest Peak (LC 1765) need the distance of every cell. For those, store dist[nxt] = dist[cell] + 1 when the cell is added. dist also works as the seen set.
Some problems ask for the reverse direction. Pacific Atlantic Water Flow (LC 417) asks which cells drain to both oceans. Start from the border cells of each ocean and move uphill, and keep the cells reached from both. This avoids a search from every cell.
60-Second Pitch
"Every rotten orange spreads at the same speed, so I use BFS with all of them in the queue at minute 0. Each round, I freeze len(queue), add one to minutes, and let every frozen cell rot its fresh neighbours. I mark a neighbour rotten when I add it, and I lower fresh_count. I stop when fresh_count reaches 0, so the last round, which rots nothing, is not counted. If the queue empties while fresh_count is above 0, I return -1. Each cell is added once and tries four neighbours. So the time is O(R * C), and the space is O(R * C) for the queue."
Common Questions
- Why is one BFS with all sources better than one BFS per source?
One BFS per source repeats work and costs O(S * R * C) for S sources. One BFS with all sources in the queue visits each cell once, so it costs O(R * C). It is also correct, because each cell is reached first by its nearest source.
- What are the time and space complexity of
orangesRotting? O(R * C) time, because each cell is added at most once and tries 4 neighbours. O(R * C) space for
queuein the worst case, such as a grid where every cell is rotten at the start.- Why do you stop when
fresh_countis 0 and not whenqueueis empty? The oranges that rot in the last useful round are added to
queue. If you wait forqueueto empty, one more round runs. It rots nothing, but it still adds one tominutes. Checkingfresh_count > 0stops before that round.- How do you get the distance of every cell, as in 01 Matrix (LC 542)?
Seed every cell with value 0 in
queueand setdistto 0 for them. When a cell is popped, give each unseen neighbourdist[cell] + 1and add it. A cell has adistentry once it is added, sodistis also theseenset.- What if the moves have different costs?
BFS is no longer correct, because the first time a cell is reached may not be the cheapest. Use Dijkstra's algorithm with a priority queue, and start it with all sources at distance 0. If the costs are only 0 or 1, a double-ended queue (deque) also works.
SWE Reasoning
Spot it
- There are many starting points, and they all spread at the same speed, such as rotting, fire, flooding or signal strength.
- The question asks for the time until everything is reached, or for each cell's distance to its nearest source.
- Running a single-source BFS from every cell would repeat work, and it could take O(R * C) searches.
- Every move costs the same, so the first time a cell is reached is the shortest.
- Some cells may be unreachable, and the problem asks you to report that, for example with -1.
The invariant, step by step
- Before the loop, every rotten orange is in
queue, andfresh_countcounts the fresh oranges. At this momentminutesis 0. - A round starts with
minutes += 1.range(len(queue))freezes the number of cells that were rotten at the end of the last round. - Each frozen cell is popped, and its fresh neighbours are marked 2. For each one,
fresh_countgoes down by 1 and the neighbour is added toqueue. - When the round ends, the frozen cells are gone, and
queueholds exactly the oranges that rotted in this round. This is the invariant for the new value ofminutes. - The loop stops when
queueis empty orfresh_countis 0. Withfresh_count > 0in the loop condition, a round that rots nothing is never counted. - If
fresh_count == 0, returnminutes. Otherwise some fresh orange could not be reached, and the answer is -1.
Traps
- Last round counted.
while queue:runs one more round afterfresh_countreaches 0. The result is one minute too large. - Only one source seeded. A fresh orange next to another rotten orange then waits for the first source. The answer is too large.
- Missing reachability check.
return minutesreturns the number of rounds when some fresh orange is never reached. The correct answer is -1. - Cell marked when popped. A fresh cell can then be added twice by two neighbours in the same round, and
fresh_countgoes down twice. Mark the cell when you add it. - No fresh orange at the start. The grid may already be fully rotten or empty. Return 0 before the loop.
- One counter where a distance per cell is needed. Walls and Gates (LC 286) and 01 Matrix (LC 542) need
distfor each cell.
Practice
Builds on Level-Order BFS, which you haven’t finished yet.
queue at the same time, so all sources spread together.Rotting Oranges (LC 994)(opens leetcode.com)
You're given an m x n grid whose cells each hold one of three values: 0 for an empty cell, 1 for a fresh orange, and 2 for a rotten one.
Each minute, rot spreads: any fresh orange touching a rotten orange along one of the four cardinal directions turns rotten too.
Work out how many minutes must pass before every orange is rotten, and return -1 if some fresh orange can never be reached.
Multi-Source BFS
all origin sources (t=0) ➔ concentric expansion ➔ shortest time| 1 | from collections import deque |
| 2 | from typing import Callable, Dict, Hashable, Iterable, List |
| 3 | |
| 4 | |
| 5 | def multi_source_bfs(sources: Iterable[Hashable], neighbors: Callable[[Hashable], Iterable[Hashable]]) -> Dict[Hashable, int]: |
| 6 | """Multi-Source BFS: the distance from every reachable cell to its nearest source. |
| 7 | Precondition: every move costs one step. |
| 8 | Every source starts at distance 0. neighbors(cell) yields the cells one step away that may be entered. |
| 9 | V = reachable cells. E = neighbour steps tried. T = the cost of one neighbors call. |
| 10 | Time: O(V * T + E) | Space: O(V) |
| 11 | """ |
| 12 | dist = {} # cell -> distance to its nearest source; doubles as the seen set |
| 13 | # 1. Seed Every Source at Distance 0: |
| 14 | # Placing every source in dist before the search starts lets them all spread |
| 15 | # together, instead of one source at a time. |
| 16 | for source in sources: |
| 17 | dist[source] = 0 |
| 18 | queue = deque(dist) # holds cells queued for this or a later ring, in enqueue order |
| 19 | |
| 20 | while queue: |
| 21 | # 2. Pop and Expand This Ring's Cell: |
| 22 | # Every move costs exactly 1 step, so the first time a cell is reached, it is |
| 23 | # reached by its nearest source, at the correct distance. |
| 24 | cell = queue.popleft() |
| 25 | for nxt in neighbors(cell): |
| 26 | if nxt not in dist: |
| 27 | # Marking a cell seen (giving it a dist entry) at enqueue time, not at |
| 28 | # pop time, stops it from being queued twice while still waiting. |
| 29 | dist[nxt] = dist[cell] + 1 |
| 30 | queue.append(nxt) |
| 31 | |
| 32 | return dist |
minutes rounds, queue holds exactly the oranges that turned rotten in round minutes, and fresh_count counts the fresh oranges not reached yet.Put every source into the queue at time 0, then run ordinary level-by-level BFS. All sources spread one ring per round, so each cell is reached first by its nearest source, and the round in which it turns is its distance to that source. The trap is the last round: count minutes only while fresh_count > 0, or the final round, which reaches nothing new, adds one minute too many.
See it run
Multi-Source BFS on grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]], step by step
minutes 0fresh_count 6len(queue) 1
The board is the grid. A cell holds 2 when rotten, 1 when fresh and 0 when empty. A row is one grid row.
sourcea cell that is 2 at minute 0popthe cell removed from queue nowrotsa fresh cell that becomes 2 in this stepqueueda cell waiting in queue
Every 2 goes into queue at minute 0: (0, 0). fresh_count = 6.
Gotcha 1 of 5
- The trap
Gotcha 1: Looping
while queuewithoutfresh_count > 0Mistakewhile queue:Fixwhile queue and fresh_count > 0:What happens: Each round adds one minute. The oranges that rot in the last useful round still go into
queue. Withwhile queue, the loop runs one more round for them. That round reaches no fresh orange, but it still adds one minute.Example: Rotting Oranges (LC 994): grid = [[2,1,1],[1,1,0],[0,1,1]]Mistake: returns 5Fix: returns 4
- There is one start cell and one target, as in Shortest Path in Binary Matrix (LC 1091), so nothing has to spread from many places at once. See Shortest-Path BFS
Deep Dive
Why starting from every source finds the nearest one
Level-Order BFS takes one start node, and round k handles the nodes at distance k from it. Multi-source BFS changes only the start. Put every source in queue before the first round. Then round k handles the cells at distance k from the nearest source.
Why the nearest source wins: every move costs one step, and the queue keeps its first in, first out order. A cell is added by the first neighbour that is popped and sees it as fresh. That neighbour is in the earliest possible round, so it is closest to some source. Any later source reaches the cell in a later round, and by then the cell is no longer fresh.
In Rotting Oranges (LC 994) with grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]], the only source is (0, 0). Round 1 rots (0, 1) and (1, 0). Round 2 rots (0, 2) and (1, 1). Round 3 rots (2, 1). Round 4 rots (2, 2). So minutes is 4.
Where minutes is counted, and the trap in the last round
minutes += 1 runs at the start of each round, before the cells of that round are popped. for _ in range(len(queue)) freezes the round size, as level_size does in Level-Order BFS. A cell that rots in this round is added behind the frozen cells, so it infects its neighbours in the next round.
Look at the last round of the example. In round 4, (2, 1) rots (2, 2), and fresh_count becomes 0. The queue still holds (2, 2). If the loop is while queue:, a fifth round starts. It pops (2, 2), finds no fresh neighbour, and still adds 1 to minutes. The result is 5 and not 4.
The loop while queue and fresh_count > 0 stops when nothing fresh is left. So minutes counts only the rounds that rotted at least one orange. If no orange is fresh at the start, fresh_count == 0 returns 0 before the loop.
Reachability, and the exact meaning of fresh_count
fresh_count is the number of fresh oranges that have not rotted yet. It goes down by 1 at the moment a cell is marked rotten and added to queue. Marking the cell at this moment stops a second neighbour from rotting it again in the same round.
When the queue empties and fresh_count is still above 0, some fresh orange had no path of fresh cells from any source. For grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]], the orange at (2, 0) has only empty neighbours, so the answer is -1. return minutes if fresh_count == 0 else -1 makes this case explicit. Without the check, the function returns 5, the number of rounds it ran, which is wrong.
Seeding every source matters. For grid = [[2, 1, 1], [1, 1, 1], [1, 1, 2]], seeding both rotten cells gives 2 minutes. Seeding only the first gives 3.
The cost, and when you need dist for every cell
Each cell is added at most once, and each pop tries 4 neighbours. For a grid with R rows and C columns, that is O(R * C) time. queue can hold O(R * C) cells, so the space is O(R * C). The card's template states O(V * T + E) for any graph.
Rotting Oranges (LC 994) needs one number, the time until the last orange rots, so a minutes counter is enough. Walls and Gates (LC 286), 01 Matrix (LC 542) and Map of Highest Peak (LC 1765) need the distance of every cell. For those, store dist[nxt] = dist[cell] + 1 when the cell is added. dist also works as the seen set.
Some problems ask for the reverse direction. Pacific Atlantic Water Flow (LC 417) asks which cells drain to both oceans. Start from the border cells of each ocean and move uphill, and keep the cells reached from both. This avoids a search from every cell.
60-Second Pitch
"Every rotten orange spreads at the same speed, so I use BFS with all of them in the queue at minute 0. Each round, I freeze len(queue), add one to minutes, and let every frozen cell rot its fresh neighbours. I mark a neighbour rotten when I add it, and I lower fresh_count. I stop when fresh_count reaches 0, so the last round, which rots nothing, is not counted. If the queue empties while fresh_count is above 0, I return -1. Each cell is added once and tries four neighbours. So the time is O(R * C), and the space is O(R * C) for the queue."
Common Questions
- Why is one BFS with all sources better than one BFS per source?
One BFS per source repeats work and costs O(S * R * C) for S sources. One BFS with all sources in the queue visits each cell once, so it costs O(R * C). It is also correct, because each cell is reached first by its nearest source.
- What are the time and space complexity of
orangesRotting? O(R * C) time, because each cell is added at most once and tries 4 neighbours. O(R * C) space for
queuein the worst case, such as a grid where every cell is rotten at the start.- Why do you stop when
fresh_countis 0 and not whenqueueis empty? The oranges that rot in the last useful round are added to
queue. If you wait forqueueto empty, one more round runs. It rots nothing, but it still adds one tominutes. Checkingfresh_count > 0stops before that round.- How do you get the distance of every cell, as in 01 Matrix (LC 542)?
Seed every cell with value 0 in
queueand setdistto 0 for them. When a cell is popped, give each unseen neighbourdist[cell] + 1and add it. A cell has adistentry once it is added, sodistis also theseenset.- What if the moves have different costs?
BFS is no longer correct, because the first time a cell is reached may not be the cheapest. Use Dijkstra's algorithm with a priority queue, and start it with all sources at distance 0. If the costs are only 0 or 1, a double-ended queue (deque) also works.
SWE Reasoning
Spot it
- There are many starting points, and they all spread at the same speed, such as rotting, fire, flooding or signal strength.
- The question asks for the time until everything is reached, or for each cell's distance to its nearest source.
- Running a single-source BFS from every cell would repeat work, and it could take O(R * C) searches.
- Every move costs the same, so the first time a cell is reached is the shortest.
- Some cells may be unreachable, and the problem asks you to report that, for example with -1.
The invariant, step by step
- Before the loop, every rotten orange is in
queue, andfresh_countcounts the fresh oranges. At this momentminutesis 0. - A round starts with
minutes += 1.range(len(queue))freezes the number of cells that were rotten at the end of the last round. - Each frozen cell is popped, and its fresh neighbours are marked 2. For each one,
fresh_countgoes down by 1 and the neighbour is added toqueue. - When the round ends, the frozen cells are gone, and
queueholds exactly the oranges that rotted in this round. This is the invariant for the new value ofminutes. - The loop stops when
queueis empty orfresh_countis 0. Withfresh_count > 0in the loop condition, a round that rots nothing is never counted. - If
fresh_count == 0, returnminutes. Otherwise some fresh orange could not be reached, and the answer is -1.
Traps
- Last round counted.
while queue:runs one more round afterfresh_countreaches 0. The result is one minute too large. - Only one source seeded. A fresh orange next to another rotten orange then waits for the first source. The answer is too large.
- Missing reachability check.
return minutesreturns the number of rounds when some fresh orange is never reached. The correct answer is -1. - Cell marked when popped. A fresh cell can then be added twice by two neighbours in the same round, and
fresh_countgoes down twice. Mark the cell when you add it. - No fresh orange at the start. The grid may already be fully rotten or empty. Return 0 before the loop.
- One counter where a distance per cell is needed. Walls and Gates (LC 286) and 01 Matrix (LC 542) need
distfor each cell.