AlgoViz
HomeBreadth-First Search

Rotting Oranges

Medium

Multi-source BFS · rot spreads one ring per minute

In simple words

Rot spreads to neighbors one minute at a time, like ripples — count the minutes until all are rotten.

The idea

Seed the queue with every rotten orange at once. Each BFS layer is one minute; fresh oranges adjacent to the current layer rot next. The number of layers is the time needed.

R
F
F
F
F
·
·
F
F
minute0
fresh6

Step 1 of 6. Every rotten orange (R) rots its fresh (F) neighbours each minute — a multi-source BFS. minute 0, fresh 6.

1/6
Optimal
timeO(rows·cols)spaceO(rows·cols)

All sources start at minute 0.

1// enqueue all rotten cells; BFS by layers,2// converting fresh neighbors, counting minutes.3while (q.length && fresh > 0) {4  minutes++;5  for (let n = q.length; n > 0; n--) spread(q.shift());6}7return fresh === 0 ? minutes : -1;

Input

grid
3 × 3

Memory

minute
0
fresh
6

Output

minute
0
fresh
6
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
grid = [[2,1,1],[1,1,0],[0,1,1]]
Output:
4
Explanation:
Rot spreads outward, taking 4 minutes to reach all.

Example 2

Input:
grid = [[2,1,1],[0,1,1],[1,0,1]]
Output:
-1
Explanation:
A fresh orange is unreachable → -1.

Example 3

Input:
grid = [[0,2]]
Output:
0
Explanation:
No fresh oranges → 0 minutes.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.