You are given a grid where each cell represents:

• 0 → empty cell
• 1 → fresh orange
• 2 → rotten orange

Every minute, any fresh orange that is adjacent (up, down, left, right) to a rotten orange also becomes rotten.

Your task:

Return the minimum number of minutes required for all oranges to become rotten.
If it is impossible, return -1.

Example:

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

Output: 4

---

Problem Understanding and Key Observations

Important behavior:

• Rot spreads in waves, one layer per minute
• Only four directional adjacency counts (no diagonals)
• If any fresh orange remains unreachable → answer is -1

What we need to track:

• When each orange becomes rotten
• How many fresh oranges remain
• The progression minute by minute

---

Logic Explained in Simple English

To think about the problem intuitively:

1. Start by locating all rotten oranges
   These are the starting points of infection.
2. Put all rotten oranges into a queue
   Because rotting spreads outward step by step.
3. Perform a breadth-first search (BFS)
   Each round of BFS represents one minute.
4. For each rotten orange, infect neighboring fresh oranges
   Newly infected oranges are added to the queue for the next minute.
5. Track how many minutes the process takes
   After BFS ends, if:
   • no fresh oranges remain → return minutes
   • some fresh oranges remain → return -1

Why BFS works perfectly:

• BFS processes things level-by-level
• Each level corresponds naturally to one minute of spread

---

Step-by-Step Solution Approach

Step 1: Scan the grid

• Count total fresh oranges
• Add all rotten oranges (value 2) to a queue

Step 2: BFS processing

While queue not empty:

• Process all oranges currently infected (one minute batch)
• Infect neighbors that are fresh
• Decrease fresh count
• Add newly rotten oranges to queue

Step 3: Track time

• Increment minute counter only when new infections occur

Step 4: Final decision

• If fresh count is zero → return minutes
• Else → return -1

---

Java Implementation

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        
        // Step 1: Initialize queue with all rotten oranges
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r] == 2) {
                    queue.offer(new int[]{r, c});
                } else if (grid[r] == 1) {
                    freshCount++;
                }
            }
        }
        
        if (freshCount == 0) return 0; // No fresh oranges
        
        int minutes = 0;
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        
        // Step 2: BFS infection spread
        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean infectedThisRound = false;
            
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                int r = curr[0], c = curr[1];
                
                for (int[] d : directions) {
                    int nr = r + d[0];
                    int nc = c + d[1];
                    
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols 
                        && grid[nr][nc] == 1) {
                        
                        grid[nr][nc] = 2;
                        freshCount--;
                        infectedThisRound = true;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
            
            if (infectedThisRound) {
                minutes++;
            }
        }
        
        return freshCount == 0 ? minutes : -1;
    }
}

---

Dry Run Example

Input grid:

[
 [2,1,1],
 [1,1,0],
 [0,1,1]
]

Initial Scan

Fresh oranges = 7
Queue initially contains position of rotten orange: (0,0)

Minute 1 spread

Newly rotten: (0,1), (1,0)
Fresh left: 5

Minute 2 spread

From new rotten positions:
Newly rotten: (0,2), (1,1)
Fresh left: 3

Minute 3 spread

Newly rotten: (2,1)
Fresh left: 2

Minute 4 spread

Newly rotten: (2,2)
Fresh left: 1 → correction: grid correction shows remaining count becomes 0

Result

All oranges rotten in 4 minutes

Output: 4

---

Time and Space Complexity

Time Complexity

O(rows × cols)
Because every cell processed at most once

Space Complexity

O(rows × cols)
Due to BFS queue in worst case

---

Common Mistakes and How to Avoid Them

Mistake 1: Incrementing minutes every loop

Increment only when at least one fresh orange becomes rotten that round.

Mistake 2: Not counting fresh oranges first

Needed to detect impossible cases.

Mistake 3: Forgetting boundary checks

Avoid array index errors.

Mistake 4: Allowing diagonal infection

Only 4-directional adjacency is valid.

Mistake 5: Returning minutes even if fresh remain

Must return -1 if any fresh orange is unreachable.