The problem
In a grid, 2 = rotten orange, 1 = fresh, 0 = empty. Every minute, each rotten orange rots its fresh neighbours (up, down, left, right). How many minutes until no fresh orange is left? Return −1 if that never happens.
Input: 211 / 110 / 011 Output: 4
Picture it
Picture a crate of oranges. All the rotten oranges start spreading at the same time, like ripples. We put every rotten orange in a queue together and spread one “wave” per minute. If some fresh orange is never reached (walled off by empty spaces), the answer is −1.
How to recognise it
- Something spreads outwards from several starting points at once, one step per unit of time.
- The question asks for the time until everything is reached, or whether that never happens.
- All starting points begin at the same moment, so there is no single source.
- Grids are small here (at most 10 × 10), but the pattern is the same one used for far larger floods.
Start with brute force
Simulate each minute literally. Scan the whole grid, and every fresh orange with a rotten neighbour becomes rotten in a copy of the grid. Repeat until a minute changes nothing, then check whether any fresh orange remains.
def rotting_brute(grid):
g, minutes = [row[:] for row in grid], 0
while True:
new = [row[:] for row in g]
changed = False
for r, c in all_cells(g):
if g[r][c] == 1 and any(g[a][b] == 2 for a, b in nbrs(g, r, c)):
new[r][c] = 2
changed = True
if not changed:
break
g, minutes = new, minutes + 1
return -1 if any(1 in row for row in g) else minutes
Each minute costs O(R·C) for the scan and the copy. In the worst case the rot snakes through a path that is about R·C/2 cells long, so there can be about R·C/2 minutes and the total is O((R·C)²). For a 10 × 10 crate that is trivial, but for 1000 × 1000 it is roughly 5 × 10^11 steps. Space is O(R·C).
From brute force to the idea
- Find the waste. Most of each scan looks at cells that cannot possibly change this minute: only oranges next to freshly rotten ones matter.
- Keep a frontier. The queue holds the oranges that rotted most recently. Start it with every rotten orange, and count the fresh ones.
- Process one minute at a time.
for _ in range(len(q))takes exactly the oranges that are in the queue right now, which is one level of the search. Their fresh neighbours rot, are queued for the next level, andfreshdrops by one each time. - Count levels. After a level is done,
minutes += 1. The loop stops as soon as the queue is empty orfreshreaches 0, so no extra minute is added after the last orange rots. - Decide the answer. If
freshis 0 returnminutes, otherwise some orange was walled off and the answer is -1.
The key idea: this is BFS started from all rotten oranges together, and each BFS level is one minute.
The key idea
Multi-source BFS: all starting points enter the queue at once, and each level is one minute. O(rows × cols).
Python solution
def oranges_rotting(grid):
q, fresh = deque(), 0
for r, c in all_cells(grid):
if grid[r][c] == 2: q.append((r, c))
if grid[r][c] == 1: fresh += 1
minutes = 0
while q and fresh:
for _ in range(len(q)):
r, c = q.popleft()
for nr, nc in nbrs(grid, r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1
def all_cells(g):
return [(r, c) for r in range(len(g))
for c in range(len(g[0]))]
def nbrs(g, r, c): # in-grid neighbours
R, C = len(g), len(g[0])
for nr, nc in ((r+1, c), (r-1, c),
(r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, ncLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O((R·C)²): up to about R·C/2 minutes, each scanning the grid | O(R·C): a copy of the grid each minute |
| Multi-source BFS (shown code) | O(R·C): each orange is queued at most once, with four neighbour checks | O(R·C): the queue and the list from all_cells; the grid is changed in place |
Edge cases
- No fresh oranges (
[[0]],[[2]],[[0,2]]): returns 0, even when there is no rotten orange. - Fresh oranges but nothing rotten (
[[1]]): returns -1. - A fresh orange cut off by empty cells (
[[2,0,1]]): returns -1. - Already all rotten (
[[2]]): returns 0. - Diagonals do not spread rot, so
[[2,1,1],[0,1,1],[1,0,1]]returns -1 because the bottom-left orange is isolated. - The grid is modified, and
dequemust be imported.
Common mistakes
- Starting a separate BFS from each rotten orange, which gives wrong times and wastes work.
- Counting minutes per orange popped instead of per level.
- Looping
while qonly, which counts one extra minute after the last orange rots. - Forgetting to check
freshat the end, so unreachable oranges return a time instead of -1. - Marking an orange rotten only when it is popped, so it can be queued twice.
Return how many fresh oranges have rotted after exactly m minutes. Describe what changes, then write it if you like.
Compare with our answer
The level-by-level loop is the same, but it runs for exactly m levels (or until the queue empties) and counts the oranges it rots.
def rotted_after(grid, m):
q, rotted = deque(), 0
for r, c in all_cells(grid):
if grid[r][c] == 2:
q.append((r, c))
for _ in range(m):
for _ in range(len(q)):
r, c = q.popleft()
for nr, nc in nbrs(grid, r, c):
if grid[nr][nc] == 1:
grid[nr][nc] = 2
rotted += 1
q.append((nr, nc))
return rotted
Time O(R·C), space O(R·C). If the queue empties early the later minutes do nothing.
A strong answer mentions: multi-source BFS, a bounded number of levels instead of a fresh counter, and why levels correspond to minutes.
1. A grid has 0s and 1s. You must write, in every cell, its distance (in steps up, down, left or right) to the nearest 1. Which approach fits best?
A multi-source BFS starts from all the 1s together, so the first time a cell is reached is its shortest distance. One search per cell repeats work, and row-by-row pointers miss vertical paths.
2. Why does the shown code loop for _ in range(len(q)) inside the while?
len(q) is fixed when the loop begins, so only the oranges rotten at the start of that minute are expanded. Newly queued ones wait for the next minute. First-in-first-out order is already provided by the deque.
3. A learner changes the last line to return minutes. Which input now returns a wrong answer?
In the first three inputs every fresh orange rots (or there are none), so the minute count is right. In [[2,0,1]] the loop ends with a fresh orange left and the learner's version returns 0, not -1.
Score 60% or more and the lesson is marked complete.