Rotting Oranges (LeetCode 994)
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.
Worked Examples
grid = [[2,1,1],[1,1,0],[0,1,1]]4grid = [[2,1,1],[0,1,1],[1,0,1]]-1grid = [[0,2]]0⚖️Formal Constraints & Bounds
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]is0,1, or2.
Core Insight
Marking oranges rotten at enqueue time prevents duplicate queue entries and models parallel infection waves accurately.
Real-World Scenario & Production Applications
Epidemiological virus contagion modeling and wildfire spread perimeter simulations.
Subproblems & Recurrence Decomposition3 Phases
Scan the entire grid. Enqueue all initial source coordinates (e.g. all rotten oranges, distance 0) and count target elements.
queue = deque()
fresh = 0
for r in range(R):
for c in range(C):
if grid[r][c] == 2: queue.append((r, c))
elif grid[r][c] == 1: fresh += 1Step-by-Step Execution Trace Table
Minute 0 (Initial Seed): Minute 1 (Infect): Minute 2 (Infect):[ 2 ] [ 1 ] [ 1 ] [ 2 ] [ 2 ] [ 1 ] [ 2 ] [ 2 ] [ 2 ][ 1 ] [ 1 ] [ 0 ] ==> [ 2 ] [ 1 ] [ 0 ] ==> [ 2 ] [ 2 ] [ 0 ][ 0 ] [ 1 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ]queue=[(0,0)], fresh=6 queue=[(0,1),(1,0)], fresh=4 queue=[(0,2),(1,1)], fresh=2 Minute 3 (Infect): Minute 4 (Final Fresh):[ 2 ] [ 2 ] [ 2 ] [ 2 ] [ 2 ] [ 2 ][ 2 ] [ 2 ] [ 0 ] ==> [ 2 ] [ 2 ] [ 0 ][ 0 ] [ 2 ] [ 1 ] [ 0 ] [ 2 ] [ 2 ]queue=[(2,1)], fresh=1 queue=[(2,2)], fresh=0 (Goal Reached! ✅) Step-by-Step Wavefront Progression
- Step 1 (Multi-Source Seed, Minute 0, d=0):
queue = [(0, 0)],fresh = 6. Scan grid at : count 6 fresh oranges, enqueue initial rotten cell(0, 0). - Step 2 (Snapshot Minute 0, level_size=1, d=0):
level_size = 1. Minute 0 wavefront starts. - Step 3 (Pop (0,0) & Infect (0,1), (1,0), d=0): Pop
(0, 0). 4-directional neighbors: infect(0, 1)and(1, 0). Mark on enqueue:grid[0][1]=2, grid[1][0]=2.fresh = 4.queue = [(0, 1), (1, 0)]. Minute advances:minutes = 1🌊. - Step 4 (Snapshot Minute 1, level_size=2, d=1):
level_size = 2. Minute 1 wavefront.queue = [(0, 1), (1, 0)]. - Step 5 (Pop (0,1) & Infect (0,2), (1,1), d=1): Pop
(0, 1). Infect(0, 2)and(1, 1). Mark on enqueuefresh = 2.queue = [(1, 0), (0, 2), (1, 1)]. - Step 6 (Pop (1,0), Diamond Convergence Guard, d=1): Pop
(1, 0). Neighbor(1, 1)is already marked 2 (visited)! Guard prevents duplicate enqueue. Minute advances:minutes = 2🌊. - Step 7 (Snapshot Minute 2, level_size=2, d=2):
level_size = 2. Minute 2 wavefront.queue = [(0, 2), (1, 1)]. - Step 8 (Pop (0,2), Blocked Neighbor (1,2)=0, d=2): Pop
(0, 2). Neighbor(1, 2)is empty (0) skip. - Step 9 (Pop (1,1) & Infect (2,1), d=2): Pop
(1, 1). Infect(2, 1). Mark on enqueuefresh = 1.queue = [(2, 1)]. Minute advances:minutes = 3🌊. - Step 10 (Snapshot Minute 3, level_size=1, d=3):
level_size = 1. Minute 3 wavefront.queue = [(2, 1)]. - Step 11 (Pop (2,1) & Infect Final (2,2), d=3): Pop
(2, 1). Infect(2, 2). Mark on enqueuefresh = 0.queue = [(2, 2)]. Minute advances:minutes = 4🌊. - Step 12 (Goal Check, fresh == 0, Complete, d=4):
fresh = 0. All oranges fully rotted. Search Complete: return4✅.
grid = [[2,1,1],[1,1,0],[0,1,1]]Expected:4| 1 | queue = deque(all_rotten_cells) |
| 2 | fresh = count_fresh() |
| 3 | minutes = 0 |
| 4 | while queue and fresh > 0: |
| 5 | for _ in range(len(queue)): |
| 6 | r, c = queue.popleft() |
| 7 | make each fresh neighbor in the 4 directions rotten, fresh -= 1, and append it to queue |
| 8 | minutes += 1 |
| 9 | return minutes if fresh == 0 else -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every earlier BFS in this pattern started from exactly one node. Here, the infection starts from potentially dozens of places at the same instant — and the fix is almost embarrassingly simple.
🪨 The Analogy: Dropping Several Stones in a Pond at Once
Picture dropping several stones into a pond at the exact same moment, instead of just one. Each stone starts its own ripple, and all the ripples expand outward in perfect sync — where two ripples meet, both arrived at that point during the very same "tick." You don't need to simulate each stone's ripple separately and then merge them; if you drop all the stones into the water before the clock starts, a single shared expanding wavefront naturally emerges.
🔑 The Key Idea in the Code
Seeding the queue with every starting point before the first level even begins is the entire adaptation — the level-by-level snapshot loop doesn't need to change at all; it just now represents "everyone one minute away from any rotten orange," not "everyone one step from a single source."
Single-source BFS instead of multi-source wavefront: Running BFS from one rotten orange at a time fails to model concurrent infection. All initial rotten oranges must be enqueued at minute 0 simultaneously.
Incrementing timer when no fresh oranges rot: Incrementing the minute counter on every level even when no adjacent fresh oranges were infected overcounts total minutes.
Isolated fresh oranges unreached: Forgetting to check if
fresh_count > 0after the queue is empty, returning elapsed minutes when fresh oranges were actually unreachable (must return-1).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Each minute, rot spreads" from every rotten orange at once, and the question is "how many minutes must pass before every orange is rotten", or -1. Many sources, one shared clock: Multi-Source BFS.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After minutes rounds, queue holds exactly the oranges that turned rotten in round minutes, and fresh_count counts the fresh oranges not reached yet. The decision: a fresh neighbour turns rotten (grid[nr][nc] = 2) and is pushed in the round that first reaches it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
return minutes if fresh_count == 0 else -1: a fresh orange walled off by empty cells is never reached, so the answer is -1, not the minutes counted so far.while queue and fresh_count > 0: the card's trap; withoutfresh_count > 0the last round reaches nothing new and adds one minute too many.if fresh_count == 0: return 0: a grid with no fresh orange needs 0 minutes, even when it has no rotten orange either.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Multi-Source BFS. Every rotten orange spreads at the same time, so I put all of them in the queue at minute zero and count the fresh ones. Then I run level-by-level BFS: each round is one minute, and in that round every orange in the queue turns its fresh neighbours rotten, which I mark right away and push for the next round. Because all sources grow one ring per round together, each fresh orange rots in the round of its nearest rotten orange, so the round count is the answer. The trap is the last round: I only start a round while fresh oranges remain, otherwise a final round that reaches nothing adds one minute too many. If the queue empties with fresh oranges left, some are walled off, and I return minus one. Each cell is pushed at most once, so it's O(R times C) time and space.
Complexity & Mathematical Proof
O(R * C)
Look at the code: the double for r in range(R): for c in range(C) scan visits each of the R · C cells once. In while queue and fresh_count > 0, a cell is pushed only when it turns from 1 to 2, so each cell is pushed at most once, and each pop checks the 4 directions with O(1) work. Scan plus checks: R · C + 4 · R · C = 5 · R · C = O(R * C).
O(R * C)
queue can hold every rotten cell at once (for example all of them at minute 0), so O(R * C). The grid is updated in place and there is no recursion (call stack O(1)); the answer is one integer.
T(R, C) = R · C (scan) + 4 · R · C (neighbour checks) = 5 · R · C = O(R * C)
Derivation Progression
for r in range(R): for c in range(C) → R · C cells
Every rotten orange is pushed and every fresh one counted, O(1) per cell.
grid[nr][nc] = 2 before queue.append((nr, nc)) → ≤ R · C pops × 4 directions
A cell is pushed only when it turns rotten, which happens once, so there are at most R · C pops with 4 checks each.
R · C + 4 · R · C = 5 · R · C = O(R * C)
Both phases are linear in the number of cells.
Variable Definitions
Number of rows in the grid
Number of columns in the grid
Memory Architecture & Bounds
O(1): no recursion
O(R * C): queue of coordinates; the grid is changed in place
O(1): the minutes count
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "Each minute, rot spreads" from every rotten orange, "how many minutes must pass before every orange is rotten": many sources on one clock, Multi-Source BFS. At scale the same shape is a nearest-source distance map computed for a whole grid in one pass.
, so at most 100 cells and 500 steps. The cost is linear in cells whatever the number of sources: a map is cells, where the queue (one coordinate pair per cell of the widest ring) and the grid itself are the memory to plan for.
The grid is changed in place (fresh cells become 2): copy it first if the caller still needs the original. On a map too large for memory, the rings can be processed in tiles, but a ring crossing a tile border must be handed to the neighbouring tile in the same round.
Core Algorithmic State Invariants
- First Arrival Is the Nearest Source
All sources start in round 0 and every ring grows by one cell per round, so the first time any ring reaches a cell, no other source is closer. That is why the round a cell turns rotten is its distance to the nearest rotten orange, and why it never needs updating.
Rotting Oranges (LeetCode 994)
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.
Worked Examples
grid = [[2,1,1],[1,1,0],[0,1,1]]4grid = [[2,1,1],[0,1,1],[1,0,1]]-1grid = [[0,2]]0⚖️Formal Constraints & Bounds
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]is0,1, or2.
Core Insight
Marking oranges rotten at enqueue time prevents duplicate queue entries and models parallel infection waves accurately.
Real-World Scenario & Production Applications
Epidemiological virus contagion modeling and wildfire spread perimeter simulations.
Subproblems & Recurrence Decomposition3 Phases
Scan the entire grid. Enqueue all initial source coordinates (e.g. all rotten oranges, distance 0) and count target elements.
queue = deque()
fresh = 0
for r in range(R):
for c in range(C):
if grid[r][c] == 2: queue.append((r, c))
elif grid[r][c] == 1: fresh += 1Step-by-Step Execution Trace Table
Minute 0 (Initial Seed): Minute 1 (Infect): Minute 2 (Infect):[ 2 ] [ 1 ] [ 1 ] [ 2 ] [ 2 ] [ 1 ] [ 2 ] [ 2 ] [ 2 ][ 1 ] [ 1 ] [ 0 ] ==> [ 2 ] [ 1 ] [ 0 ] ==> [ 2 ] [ 2 ] [ 0 ][ 0 ] [ 1 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ]queue=[(0,0)], fresh=6 queue=[(0,1),(1,0)], fresh=4 queue=[(0,2),(1,1)], fresh=2 Minute 3 (Infect): Minute 4 (Final Fresh):[ 2 ] [ 2 ] [ 2 ] [ 2 ] [ 2 ] [ 2 ][ 2 ] [ 2 ] [ 0 ] ==> [ 2 ] [ 2 ] [ 0 ][ 0 ] [ 2 ] [ 1 ] [ 0 ] [ 2 ] [ 2 ]queue=[(2,1)], fresh=1 queue=[(2,2)], fresh=0 (Goal Reached! ✅) Step-by-Step Wavefront Progression
- Step 1 (Multi-Source Seed, Minute 0, d=0):
queue = [(0, 0)],fresh = 6. Scan grid at : count 6 fresh oranges, enqueue initial rotten cell(0, 0). - Step 2 (Snapshot Minute 0, level_size=1, d=0):
level_size = 1. Minute 0 wavefront starts. - Step 3 (Pop (0,0) & Infect (0,1), (1,0), d=0): Pop
(0, 0). 4-directional neighbors: infect(0, 1)and(1, 0). Mark on enqueue:grid[0][1]=2, grid[1][0]=2.fresh = 4.queue = [(0, 1), (1, 0)]. Minute advances:minutes = 1🌊. - Step 4 (Snapshot Minute 1, level_size=2, d=1):
level_size = 2. Minute 1 wavefront.queue = [(0, 1), (1, 0)]. - Step 5 (Pop (0,1) & Infect (0,2), (1,1), d=1): Pop
(0, 1). Infect(0, 2)and(1, 1). Mark on enqueuefresh = 2.queue = [(1, 0), (0, 2), (1, 1)]. - Step 6 (Pop (1,0), Diamond Convergence Guard, d=1): Pop
(1, 0). Neighbor(1, 1)is already marked 2 (visited)! Guard prevents duplicate enqueue. Minute advances:minutes = 2🌊. - Step 7 (Snapshot Minute 2, level_size=2, d=2):
level_size = 2. Minute 2 wavefront.queue = [(0, 2), (1, 1)]. - Step 8 (Pop (0,2), Blocked Neighbor (1,2)=0, d=2): Pop
(0, 2). Neighbor(1, 2)is empty (0) skip. - Step 9 (Pop (1,1) & Infect (2,1), d=2): Pop
(1, 1). Infect(2, 1). Mark on enqueuefresh = 1.queue = [(2, 1)]. Minute advances:minutes = 3🌊. - Step 10 (Snapshot Minute 3, level_size=1, d=3):
level_size = 1. Minute 3 wavefront.queue = [(2, 1)]. - Step 11 (Pop (2,1) & Infect Final (2,2), d=3): Pop
(2, 1). Infect(2, 2). Mark on enqueuefresh = 0.queue = [(2, 2)]. Minute advances:minutes = 4🌊. - Step 12 (Goal Check, fresh == 0, Complete, d=4):
fresh = 0. All oranges fully rotted. Search Complete: return4✅.
grid = [[2,1,1],[1,1,0],[0,1,1]]Expected:4| 1 | queue = deque(all_rotten_cells) |
| 2 | fresh = count_fresh() |
| 3 | minutes = 0 |
| 4 | while queue and fresh > 0: |
| 5 | for _ in range(len(queue)): |
| 6 | r, c = queue.popleft() |
| 7 | make each fresh neighbor in the 4 directions rotten, fresh -= 1, and append it to queue |
| 8 | minutes += 1 |
| 9 | return minutes if fresh == 0 else -1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Every earlier BFS in this pattern started from exactly one node. Here, the infection starts from potentially dozens of places at the same instant — and the fix is almost embarrassingly simple.
🪨 The Analogy: Dropping Several Stones in a Pond at Once
Picture dropping several stones into a pond at the exact same moment, instead of just one. Each stone starts its own ripple, and all the ripples expand outward in perfect sync — where two ripples meet, both arrived at that point during the very same "tick." You don't need to simulate each stone's ripple separately and then merge them; if you drop all the stones into the water before the clock starts, a single shared expanding wavefront naturally emerges.
🔑 The Key Idea in the Code
Seeding the queue with every starting point before the first level even begins is the entire adaptation — the level-by-level snapshot loop doesn't need to change at all; it just now represents "everyone one minute away from any rotten orange," not "everyone one step from a single source."
Single-source BFS instead of multi-source wavefront: Running BFS from one rotten orange at a time fails to model concurrent infection. All initial rotten oranges must be enqueued at minute 0 simultaneously.
Incrementing timer when no fresh oranges rot: Incrementing the minute counter on every level even when no adjacent fresh oranges were infected overcounts total minutes.
Isolated fresh oranges unreached: Forgetting to check if
fresh_count > 0after the queue is empty, returning elapsed minutes when fresh oranges were actually unreachable (must return-1).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Each minute, rot spreads" from every rotten orange at once, and the question is "how many minutes must pass before every orange is rotten", or -1. Many sources, one shared clock: Multi-Source BFS.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
After minutes rounds, queue holds exactly the oranges that turned rotten in round minutes, and fresh_count counts the fresh oranges not reached yet. The decision: a fresh neighbour turns rotten (grid[nr][nc] = 2) and is pushed in the round that first reaches it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
return minutes if fresh_count == 0 else -1: a fresh orange walled off by empty cells is never reached, so the answer is -1, not the minutes counted so far.while queue and fresh_count > 0: the card's trap; withoutfresh_count > 0the last round reaches nothing new and adds one minute too many.if fresh_count == 0: return 0: a grid with no fresh orange needs 0 minutes, even when it has no rotten orange either.
The 60-Second Interview Pitch
Say this out loud before you type a single line
This is Multi-Source BFS. Every rotten orange spreads at the same time, so I put all of them in the queue at minute zero and count the fresh ones. Then I run level-by-level BFS: each round is one minute, and in that round every orange in the queue turns its fresh neighbours rotten, which I mark right away and push for the next round. Because all sources grow one ring per round together, each fresh orange rots in the round of its nearest rotten orange, so the round count is the answer. The trap is the last round: I only start a round while fresh oranges remain, otherwise a final round that reaches nothing adds one minute too many. If the queue empties with fresh oranges left, some are walled off, and I return minus one. Each cell is pushed at most once, so it's O(R times C) time and space.
Complexity & Mathematical Proof
O(R * C)
Look at the code: the double for r in range(R): for c in range(C) scan visits each of the R · C cells once. In while queue and fresh_count > 0, a cell is pushed only when it turns from 1 to 2, so each cell is pushed at most once, and each pop checks the 4 directions with O(1) work. Scan plus checks: R · C + 4 · R · C = 5 · R · C = O(R * C).
O(R * C)
queue can hold every rotten cell at once (for example all of them at minute 0), so O(R * C). The grid is updated in place and there is no recursion (call stack O(1)); the answer is one integer.
T(R, C) = R · C (scan) + 4 · R · C (neighbour checks) = 5 · R · C = O(R * C)
Derivation Progression
for r in range(R): for c in range(C) → R · C cells
Every rotten orange is pushed and every fresh one counted, O(1) per cell.
grid[nr][nc] = 2 before queue.append((nr, nc)) → ≤ R · C pops × 4 directions
A cell is pushed only when it turns rotten, which happens once, so there are at most R · C pops with 4 checks each.
R · C + 4 · R · C = 5 · R · C = O(R * C)
Both phases are linear in the number of cells.
Variable Definitions
Number of rows in the grid
Number of columns in the grid
Memory Architecture & Bounds
O(1): no recursion
O(R * C): queue of coordinates; the grid is changed in place
O(1): the minutes count
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "Each minute, rot spreads" from every rotten orange, "how many minutes must pass before every orange is rotten": many sources on one clock, Multi-Source BFS. At scale the same shape is a nearest-source distance map computed for a whole grid in one pass.
, so at most 100 cells and 500 steps. The cost is linear in cells whatever the number of sources: a map is cells, where the queue (one coordinate pair per cell of the widest ring) and the grid itself are the memory to plan for.
The grid is changed in place (fresh cells become 2): copy it first if the caller still needs the original. On a map too large for memory, the rings can be processed in tiles, but a ring crossing a tile border must be handed to the neighbouring tile in the same round.
Core Algorithmic State Invariants
- First Arrival Is the Nearest Source
All sources start in round 0 and every ring grows by one cell per round, so the first time any ring reaches a cell, no other source is closer. That is why the round a cell turns rotten is its distance to the nearest rotten orange, and why it never needs updating.