Rotting Oranges

Rotting Oranges

What is this problem about?

The Rotting Oranges interview question gives you a 2D grid where each cell is either empty (0), a fresh orange (1), or a rotten orange (2). Every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. Determine the minimum number of minutes until no fresh oranges remain, or return -1 if it is impossible.

Why is this asked in interviews?

This problem is asked at Apple, Uber, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, Adobe, and many more companies because it is the canonical multi-source BFS problem. Starting BFS from all rotten oranges simultaneously models "spreading infection" — directly applicable to epidemic spread modeling, network packet propagation, fire simulation, and distance-from-sources problems in graphs.

Algorithmic pattern used

The pattern is multi-source BFS (Breadth-First Search). Initialize the BFS queue with all initially rotten oranges. Count fresh oranges. Run BFS level by level — each BFS level represents one minute passing. For each rotten orange in the queue, spread to its 4 neighbors. If a neighbor is fresh, mark it rotten, decrement the fresh count, and add it to the queue. Track the number of BFS levels processed. If fresh count reaches 0, return the level count. If fresh count is still > 0 after BFS, return -1.

Example explanation

Grid:

2 1 1
1 1 0
0 1 1

Initial queue: [(0,0)]. Fresh count: 6.

Minute 1: Rot neighbors of (0,0) → (0,1) and (1,0). Fresh count=4. Minute 2: Rot neighbors of (0,1) and (1,0) → (0,2), (1,1). Fresh count=2. Minute 3: Rot (2,1). Fresh count=1. Minute 4: Rot (2,2). Fresh count=0.

Answer: 4.

Common mistakes candidates make

• Starting BFS from only one rotten orange — must initialize from ALL rotten oranges simultaneously for multi-source BFS.
• Counting BFS levels as queue.size() calls — use a level-by-level approach (process all nodes at the current level before incrementing the minute counter).
• Forgetting to return -1 when some fresh oranges remain unreachable.
• Not handling grids with no fresh oranges (answer is 0) or all rotten from the start.

Interview preparation tip

For the Rotting Oranges coding problem, the BFS and matrix interview pattern is multi-source BFS — one of the most important graph patterns. The key insight: all initial rotten oranges spread simultaneously, so initialize the queue with ALL of them before starting BFS. Interviewers at Citadel and Lyft often follow up with "what if diagonal adjacency is included?" — simply extend the 4-directional delta array to 8 directions. Master multi-source BFS — it appears in dozens of grid problems.