Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Rotting Oranges

LeetCode #994Medium
Multi-source BFS · rot spreads one ring per minute

Given a grid whose cells are empty, hold a fresh orange, or hold a rotten orange, each minute every fresh orange adjacent to a rotten one becomes rotten; return the minimum number of minutes until no fresh orange remains, or -1 if some fresh orange can never rot.

Asked atAmazonGoogleMicrosoft
step 1 / 17
3 × 3 grid · 0 empty · 1 fresh · 2 rotten
2
1
1
1
1
0
0
1
1
queue · rotten frontier
front →
(empty)
← back
Multi-source BFS by minute
1queue = all rotten cells // multi-source seed
2fresh = count of 1s
3minute = 0
4while queue not empty and fresh > 0:
5 minute++
6 for each cell in this minute’s batch:
7 for each fresh neighbour:
8 rot it, fresh--, enqueue it
9 queue = newly rotted
10return fresh == 0 ? minute : -1
state
  • fresh6
  • minute0

line 1Rotting Oranges: every minute, each rotten orange (2) rots its four fresh neighbours (1). We want the minute when the LAST fresh orange rots. The rot spreads outward in rings — exactly one cell-step per minute — which is precisely what BFS levels measure. So this is a shortest-time-to-infect problem.