Rotting Oranges
You get a grid as a list of rows of equal length. Each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that shares a side with a rotten orange, up, down, left or right, turns rotten. Return the number of minutes until no fresh orange is left, or -1 if some fresh orange can never rot. A grid with no fresh oranges at the start needs 0 minutes.
Function
- gridinteger-2d-array
- the grid, one list of 0, 1 and 2 per row
- Returnsinteger
- the minutes until no orange is fresh, or -1 if that never happens
Constraints
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- Every row has the same length.
- Each
grid[i][j]is0,1or2.
Examples
- Input
- grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
- Output
- 6
- Explanation
- Cells are (row, column). The rot follows the only path from (0,0) and reaches (2,3) at minute 5. The orange at (1,3) touches only (2,3), so it rots last, at minute 6.
- Input
- grid = [[2, 1, 0], [0, 0, 1]]
- Output
- -1
- Explanation
- The orange at (1,2) has empty cells above it and to its left, and the edge of the grid below and to its right. No rot can reach it, so the answer is -1.
- Input
- grid = [[0, 2, 0, 2]]
- Output
- 0
- Explanation
- There is no fresh orange at the start, so no time has to pass and the answer is 0.
Follow-up
Suppose each fresh orange needs its own number of minutes to rot once a neighbour is rotten. How would you find the finishing time then?
Hints
Open them one at a time. Each one gives away a little more.
Think of the rot as spreading in waves. Which oranges can turn rotten at minute 3? Only fresh oranges next to an orange that turned at minute 2.
Run one breadth first search from every rotten orange at once: put all of them in the queue before the search starts. The queue then always holds the edge of the rot.
Work through the queue one level at a time: read its size, take that many cells, and count one minute per level. Count the fresh oranges up front and lower the count as they rot, so you can stop the moment it reaches 0, and return -1 if the queue runs dry first.
Solution
The rot spreads from every rotten orange at once, one cell a minute, so the answer is a distance: how far the farthest fresh orange is from its nearest rotten orange. Breadth first search measures that when every rotten orange starts in the queue and each level of the queue is one minute.
Simulate minute by minute
Correct, but does not finish on the largest tests
Intuition
Each minute, scan the whole grid and list every fresh orange that touches a rotten one. Then rot them all and add one to the clock. Stop when a scan finds nothing to rot; if a fresh orange is left, return -1.
List first, rot after. If you rot an orange in the middle of a scan, a cell later in the same scan sees it as rotten, and the rot crosses several cells in one minute.
Each minute scans all rows × cols cells, and the minutes can approach the number of cells: a winding path on a 150 × 150 grid needs 11,324 minutes, about 2.5 × 10^8 cell checks.
Algorithm
- Set minutes to 0.
- Scan the grid and list every fresh orange that has a rotten neighbour.
- If the list is empty, stop. Otherwise turn every listed orange rotten, add 1 to minutes, and scan again.
- Return -1 if a fresh orange is left, else minutes.
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
minutes = 0
while True:
# Find every fresh orange that touches a rotten one right now.
to_rot = []
for r in range(rows):
for c in range(cols):
if grid[r][c] != 1:
continue
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 2:
to_rot.append((r, c))
break
if not to_rot:
break
# Rot them only after the scan, so the rot moves one step a minute.
for r, c in to_rot:
grid[r][c] = 2
minutes += 1
for row in grid:
if 1 in row:
return -1
return minutesMulti-source BFS by levels
Intuition
The only oranges that can rot at minute t+1 are fresh neighbours of the oranges that rotted at minute t, so keep exactly those in a queue. Seed it with every orange that is rotten at minute 0. A fresh orange rots at the minute equal to its distance from the nearest rotten orange, and a breadth first search seeded with all the sources reaches each cell first from whichever source is closest.
Work in levels. At the start of a minute the queue holds the oranges that rotted last minute; take exactly that many from the front, rot their fresh neighbours and add them to the back. What remains is the next frontier.
Count the fresh oranges first and stop when the count reaches 0, or the last level adds a minute in which nothing rots. Each cell enters the queue at most once: O(rows × cols).
Algorithm
- Put every rotten orange in a queue and count the fresh ones.
- Set minutes to 0. While the queue is not empty and fresh oranges remain, add 1 to minutes and note the queue's size k.
- Take k oranges from the front. For each fresh neighbour inside the grid, mark it rotten, lower the fresh count, and add it to the back.
- When the loop ends, return minutes if the fresh count is 0, else -1.
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
# Every orange that is rotten at minute 0 starts in the queue.
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue and fresh > 0:
minutes += 1
# The queue holds exactly the oranges that went rotten last minute.
# Rot their fresh neighbours; those become the next minute's queue.
for _ in range(len(queue)):
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1
Pitfalls and edge cases
- Counting a minute for the last level. If the loop runs until the queue is empty, its final pass rots nothing and still adds 1. Stop as soon as no fresh orange is left.
- Searching from each rotten orange in turn. The first search claims every orange it reaches with its own clock:
[[2, 1, 1, 1, 1, 1, 1, 2]]then gives 6 minutes, not 3. - Returning -1 because there is no rotten orange. With no fresh orange either, nothing has to happen:
[[0]]returns 0. - Marking an orange rotten when it leaves the queue, not when it enters. An orange next to two rotten ones then goes in twice, and the fresh count drops below zero.
Frequently asked questions3
What is the time complexity of Rotting Oranges?
O(rows × cols) with breadth first search: the first scan reads every cell once, and each orange enters the queue at most once and checks four neighbours. The queue takes O(rows × cols) space in the worst case.
Why use BFS and not DFS for Rotting Oranges?
Breadth first search visits cells in order of their distance from the sources, and distance is time here: level k is the set of oranges that rot at minute k. Depth first search can reach a cell by a long detour first, then has to revisit it each time it finds a shorter route.
Can you solve Rotting Oranges without changing the grid?
Yes. Keep a separate visited array and check it instead of writing 2 into the grid. That costs O(rows × cols) extra memory, which the queue can need anyway, and it leaves the caller's grid as it was.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def orangesRotting(grid):
# Write code hereTest #1
Test #2
Test #3
Argument
grid = [[2, 1, 1, 0], [0, 1, 0, 1], [1, 1, 1, 1]]
Expected Output
6