Rotten Oranges

Medium

Multi-source BFS, one minute per level

Problem

In a grid of fresh (1) and rotten (2) oranges, every minute a rotten orange rots its 4-adjacent fresh neighbours. Return the minutes until no fresh orange remains, or -1 if impossible.

In simple words

Spread rot in waves from all rotten oranges at once (BFS); the number of waves is the time.

The idea

Seed the queue with every rotten orange so all sources spread simultaneously, then expand level by level counting minutes. Because BFS advances uniformly, the level number is the elapsed time.

The trick

Push all initial rotten oranges before starting.
Count a minute only when the next level is non-empty.
Return -1 if any fresh orange survives.

←→stepspaceplay

minute0

fresh6

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.