Rotting Oranges

Medium#994grid

A grid holds empty cells, fresh oranges and rotten ones. Every minute each rotten orange spoils the fresh oranges right above, below, left and right of it. Find how many minutes pass until no fresh orange is left, or -1 if some never rot. Our example: RFF. / F.FF / FF.R (R rotten, F fresh, . empty) — the answer is 3.

994 Rotting OrangesWalkthrough · 1×

Example: find the minutes until every orange in RFF. / F.FF / FF.R is rotten.

01230120FFFFFFF0queuefront on the left(0, 0)(2, 3)
fresh orange, Frotten at the minute shown, in the queuecurrent cellneighbour rotting nowrotten, doneempty cell

Both rotten oranges, (0, 0) and (2, 3), go into the queue at once: both start at minute 0

01/53
restart · back · play · step
Speed
1function orangesRotting(grid):
2 queue = every rotten cell
3 fresh = number of fresh cells
4 minutes = 0
5 while queue is not empty and fresh > 0:
6 repeat queue.size times:
7 (r, c) = queue.popFront()
8 for each fresh neighbour (nr, nc):
9 grid[nr][nc] = rotten
10 fresh = fresh - 1
11 queue.pushBack((nr, nc))
12 minutes = minutes + 1
13 if fresh > 0:
14 return -1
15 return minutes
state
queue
[(0, 0), (2, 3)]
fresh
–
minutes
–
r
–
c
–
nr
–
nc
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. All rotten oranges start in the queue together, so the waves spread from every one of them at the same pace.
  2. One round takes exactly the cells that were in the queue at its start: those rotted in the previous minute, so a round is one minute.
  3. Each fresh orange is counted down once, when it first rots. When fresh hits 0 the loop stops; if the queue runs dry first, some orange is cut off and the answer is -1.

Complexity

Time O(rows · cols): each cell enters the queue at most once and checks four neighbours. Memory O(rows · cols) for the queue.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.