Quick Learning Path for DSA Rotten Oranges 🍊

I’ll teach you the Rotten Oranges problem from scratch . Imagine you have a grid of oranges. Some are already rotten. Every minute, rotten oranges infect adjacent fresh oranges. How long until all are rotten or is it impossible? This is the Rotten Oranges problem . it’s a perfect gateway into understanding multi-source BFS (Breadth-First Search) and level-order traversal with queue data structures.

Let me break this down and build your understanding step by step so that you truly understand it:

<script src=”https://gist.github.com/K81094/4c2af1aea87b3fe8bb171254e986dca2.js"></script>

Step 1: Understand the Problem

Imagine a grid of oranges:

• 1 = fresh orange (good to eat)
• 2 = rotten orange (bad, will spread)
• 0 = empty cell

Every minute, rotten oranges “infect” all adjacent fresh oranges (up, down, left, right-not diagonal).

Goal: Find minimum time until all oranges are rotten, or -1 if impossible.

Step 2: Why BFS? (The Aha Moment)

This looks like a grid problem, so you might think DFS, right? Wrong!

This is actually a shortest path problem disguised as an orange problem:

• ❌ DFS explores deep and might take forever (wrong time)
• ✅ BFS explores level-by-level (perfect for “time” = levels)

Think of it like pandemic spread: Day 1 infects neighbors, Day 2 infects THEIR neighbors, etc.

Step 3: Multi-Source BFS (The Key Insight)

Normal BFS starts from 1 source node. Here, we have multiple rotten oranges spreading simultaneously.

Solution: Add ALL rotten oranges to the queue at the start!

Initial state:      After minute 1:     After minute 2:
2 1 1              2 2 1               2 2 2
1 1 0      →       2 1 0       →       2 2 0
0 1 1              0 1 1               0 2 1

All rotten oranges attack together each minute.

Step 4: The Algorithm in Plain English

1. Find all rotten oranges → add to queue
2. Count all fresh oranges
3. While queue is not empty:
   - Increment time (this = 1 minute)
   - For each rotten orange (at this level):
     - Check 4 neighbors
     - If fresh orange found:
       * Turn it rotten
       * Add to queue
       * Decrement fresh counter
4. If any fresh left → return -1 (impossible)
   Else → return time taken

Step 5: Code Walkthrough

The key parts:

java

// Step 1: Initialize with ALL rotten oranges
Queue<int[]> queue = new LinkedList<>();
int freshCount = 0;

for (int i = 0; i < rows; i++) {
    for (int j = 0; j < cols; j++) {
        if (grid[i][j] == 2) queue.offer(new int[]{i, j});
        if (grid[i][j] == 1) freshCount++;
    }
}
// Step 2: Multi-source BFS
int minutes = 0;
int[][] directions = {{-1,0}, {1,0}, {0,-1}, {0,1}}; // 4 neighbors
while (!queue.isEmpty() && freshCount > 0) {
    minutes++;
    int size = queue.size();  // ← IMPORTANT: process only CURRENT level

    for (int i = 0; i < size; i++) {  // ← Process all rotten at this minute
        int[] cell = queue.poll();

        for (int[] dir : directions) {
            int newRow = cell[0] + dir[0];
            int newCol = cell[1] + dir[1];

            // Check bounds and if it's fresh
            if (valid && grid[newRow][newCol] == 1) {
                grid[newRow][newCol] = 2;  // Turn rotten
                freshCount--;              // Count down
                queue.offer(new int[]{newRow, newCol});
            }
        }
    }
}
return freshCount == 0 ? minutes : -1;

Critical Part: Why int size = queue.size()?

This ensures we process only the rotten oranges from the current minute, not the newly added ones:

Minute 0: Queue = [A, B, C] (all rotten)
After processing A: Queue = [B, C, D, E] (D, E are newly rotten)
✓ We only process A, B, C this minute (size = 3)
✗ If we didn't track size, we'd process D, E in SAME minute (wrong!)

Try This Exercise

Test your understanding with this grid:

2 1 1
1 1 0
0 1 1

Trace through:

• Minute 0: Rotten at (0,0)
• Minute 1: (0,1) and (1,0) become rotten
• Minute 2: (0,2), (1,1) become rotten
• Minute 3: (2,1) becomes rotten
• Minute 4: (2,2) becomes rotten
• Answer: 4 minutes

Complexity

• Time: O(m × n) — we visit each cell once
• Space: O(m × n) — queue can have all cells