Rotten Oranges

Given an R × C grid where each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange), every minute any fresh orange 4-directionally adjacent to a rotten one becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if that's impossible.

Hints

· Stuck? Reveal one nudge at a time.

All rotten oranges spread at the same time — seed them all into one BFS at minute 0.

Each BFS layer corresponds to one minute.

Track the fresh count; if any remain unreached, return -1.

Common doubts

Rot spreads from every rotten orange simultaneously, so all of them must be at distance 0; a single source would overstate the time.

Count fresh oranges initially and decrement as they rot; any left after BFS can never be reached.

0 — nothing needs to rot.

Interview follow-ups

· What an interviewer asks next.

Use 8 directions; more oranges become reachable and times shrink.

After BFS, the cells still equal to 1 are exactly those.

Fun facts

LeetCode 994 — the archetypal multi-source BFS problem.
The same 'seed all sources' idea solves nearest-distance and fire-spread grids.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Rot spreads outward; the last fresh orange rots at minute 4.

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
The bottom-left orange is never adjacent to rot.

Constraints

- 1 <= R, C <= 300 - grid[i][j] is 0, 1, or 2

Rot spreads one ring per minute from every rotten orange simultaneously — that's textbook multi-source BFS. Seed the queue with all rotten oranges at time 0, then BFS outward; the time stamp when the last fresh orange rots is the answer. Count fresh oranges up front and decrement as they rot: if any remain unreachable at the end, return -1.

Seeding every source at once is what makes the BFS "layers" line up with minutes — a single-source BFS would give the wrong timing. O(R·C).

Prerequisites

Before you start

· Concepts used directly in the solution.

Multi-source BFS. all rotten oranges start at time 0 in one queue.

Fresh counter. detect the impossible case (some fresh never rot).

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Do all rotten oranges spread at once?”

Yes — simultaneously each minute.

“When is it -1?”

When a fresh orange has no path of adjacencies to any rotten one.

The ideal opening — say it like this

I seed every rotten orange into a BFS at minute 0 and spread outward; the last minute stamped is the answer.

I track the fresh count and return -1 if any fresh orange is never reached.

Understand the problem

Worked example — grid = [[2,1,1],[1,1,0],[0,1,1]]

min0: (0,0) rotten
min1: (0,1),(1,0) rot
min2: (0,2),(1,1) rot
min3: (2,1) rot
min4: (2,2) rot -> answer 4

Key observations

1Aha

One BFS layer = one minute

Multi-source BFS distances are exactly the rot times.

2Aha

Seed all rotten at time 0

Simultaneous spread requires all sources in the initial queue.

3Aha

Leftover fresh ⇒ -1

A fresh orange unreachable from any source can never rot.

Brute force vs optimal

	Minute simulation	Multi-source BFS
Idea	Each minute, scan the grid and rot neighbours	One BFS from all rotten sources
Time	O(R·C · minutes)	O(R·C)
Timing	explicit rounds	BFS layers

Both give the same minute count; BFS avoids re-scanning the grid each round. Full code is in the Approaches selector below.

Summary

Key takeaway

Multi-source BFS from every rotten orange at time 0; the last layer's time is the answer. If any fresh orange is never reached, return -1. O(R·C).

queue = all rotten at t=0; count fresh
BFS: rot fresh neighbours at t+1, fresh--
return fresh > 0 ? -1 : maxTime