Introduction

The Rotten Oranges problem involves spreading rot across a grid.

Grid values:

  • 0 → empty cell

  • 1 → fresh orange

  • 2 → rotten orange

Every minute:

  • rotten oranges infect adjacent fresh oranges

The task is to:

  • find minimum time required
    to rot all oranges

If impossible:

  • return -1

This problem is one of the most important applications of:

 Multi Source BFS

This problem helps in understanding:

  • BFS traversal

  • grid processing

  • shortest time spread

  • level-order traversal

Example

Input:grid =
[
 [2,1,1],
 [1,1,0],
 [0,1,1]
]

Output:
4

Explanation:
Minute 1:
[
 [2,2,1],
 [2,1,0],
 [0,1,1]
]

Minute 2:
[
 [2,2,2],
 [2,2,0],
 [0,1,1]
]

All oranges rot in 4 minutes.

Constraints

1 <= rows, cols <= 10^2grid[i][j] is:0, 1, or 2

Approach 1 : Brute Force Simulation

Explanation

The simplest way is:

  1. Traverse entire grid repeatedly

  2. Spread rot manually

  3. Count minutes

This works but repeatedly scanning grid increases complexity.

Steps

  1. Traverse grid.

  2. Mark fresh oranges to rot.

  3. Update grid after traversal.

  4. Increase time.

  5. Repeat until no changes occur.

Dry Run

Input:[
 [2,1,1],
 [1,1,0],
 [0,1,1]
]

Minute 1:
Adjacent oranges rot

Minute 2:
More oranges rot

Continue simulation...

Final Result:
4
Brute Force Code

Complexity Analysis

Time Complexity: O((m*n)²)Explanation:Entire grid is repeatedly scanned.

Space Complexity: O(m*n)
Explanation:
Temporary storage is used.

Approach 2 : Multi Source BFS

Explanation

The optimized solution uses:

 Multi Source BFS

Idea:

  • all rotten oranges act as BFS sources

  • every BFS level represents:

    • one minute

Process:

  1. Add all rotten oranges to queue

  2. Spread rot level by level

  3. Count minutes

This naturally models infection spread.

Steps

  1. Add all rotten oranges to queue.

  2. Count fresh oranges.

  3. Perform BFS traversal.

  4. Rot adjacent fresh oranges.

  5. Reduce fresh count.

  6. Return total minutes.

Dry Run

Initial Queue:[(0,0)]

Minute 1:
(0,1)
(1,0)

Minute 2:
(0,2)
(1,1)

Minute 3:
(2,1)

Minute 4:
(2,2)

Final Result:
4

Multi Source BFS Code

Complexity Analysis

Time Complexity: O(m * n)Explanation:
Each cell is processed once.

Space Complexity: O(m * n)
Explanation:
Queue stores grid cells.

Edge Cases

  1. No fresh oranges

  2. No rotten oranges

  3. Single cell grid

  4. Impossible infection spread

  5. Entire grid already rotten

Why This Problem is Important

Rotten Oranges helps in understanding:

  1. Multi Source BFS

  2. Grid traversal

  3. Level-order processing

  4. Time-based spreading

  5. Queue traversal

It is one of the most important BFS interview problems.

Real-World Applications

Multi-source BFS concepts are used in:

  1. Virus spread simulation

  2. Fire spread systems

  3. Network broadcasting

  4. Flood fill problems

  5. Shortest time propagation systems

Common Mistakes

  1. Forgetting all BFS sources

  2. Incorrect minute counting

  3. Missing fresh orange tracking

  4. Revisiting already rotten cells

Interview Tips

Interviewers often expect:

  1. Multi-source BFS explanation

  2. Level-order traversal understanding

  3. Time complexity reasoning

Always explain:

  • why all rotten oranges start together

  • why each BFS level equals one minute

  • how fresh orange count avoids rescanning

Related Questions

  1. Binary Tree Level Order Traversal

  2. Word Ladder

  3. Open the Lock

  4. Flood Fill

  5. Number of Islands

Final Takeaway

The Rotten Oranges problem is a fundamental multi-source BFS problem that teaches level-order traversal and time-based grid propagation techniques. Understanding this problem builds a strong foundation for advanced graph and BFS interview problems.