Rotting Oranges
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Each minute every fresh orange next to a rotten one (up, down, left, right) turns rotten. Return the minutes until no fresh orange is left, or -1 if impossible.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Why can a single BFS from one orange not give the answer?
- Hint 2Put ALL rotten oranges in the queue first and count how many fresh ones exist.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Rot spreading in a crate of fruit. At minute 0 every rotten orange is a source. In each minute all currently rotten oranges spoil their fresh neighbours simultaneously. You count minutes by waves: process everything in the queue right now, that is one minute.
- The obvious way
Simulate minute by minute scanning the whole grid: O((rows x columns)²).
- The key insight
Queue all rotten oranges and count fresh ones. While the queue is non-empty and fresh oranges remain, spend one minute: process exactly the oranges currently queued, rot each one's fresh neighbours (reduce the fresh count, queue them). At the end, if fresh > 0 return -1, else minutes.
- The algorithm
- Queue every rotten orange; count fresh.
- While the queue has items and fresh > 0: minutes + 1.
- Process this wave: rot each fresh neighbour, queue it.
- fresh > 0 at the end: -1. Else minutes.
Watch it run
Examplegrid rows: 2 1 1 / 1 1 0 / 0 1 1
Minute 0: only the top-left orange is rotten. 6 fresh oranges remain.
fresh = 6
Where people slip
- No fresh oranges at the start means 0 minutes, not -1: the loop condition handles it.
- Process exactly the oranges in the queue at the start of the minute (the wave size).
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import deque
def oranges_rotting(grid):
rows, columns = len(grid), len(grid[0])
rotten = deque()
fresh = 0
for row in range(rows):
for column in range(columns):
if grid[row][column] == 2:
rotten.append((row, column)) # every rotten orange is a source
elif grid[row][column] == 1:
fresh += 1
minutes = 0
while rotten and fresh > 0:
minutes += 1 # one wave = one minute
for _ in range(len(rotten)):
r, c = rotten.popleft()
for next_row, next_column in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= next_row < rows and 0 <= next_column < columns and grid[next_row][next_column] == 1:
grid[next_row][next_column] = 2
fresh -= 1
rotten.append((next_row, next_column))
return minutes if fresh == 0 else -1Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.