Rotting Oranges Java Solution with BFS

The rotting oranges problem requires finding the minimum time for all fresh oranges to become rotten in a grid, where each minute fresh oranges adjacent to rotten ones also rot. This classic BFS application demonstrates multi-source shortest path computation in 2D grids.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What are the constraints on the grid dimensions (e.g., max rows/columns)?
2. Can we mutate the input grid during our solution, or must we work with a copy?
3. What should we return if there are no fresh oranges initially, or if some fresh oranges can never rot?
4. Are we guaranteed that the input grid will only contain 0, 1, or 2 values?
5. What's the expected time complexity for the solution (e.g., can we do better than O(m²n²))?

Restatement in my own words: We have a grid where each cell represents an orange with three possible states:

• 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 becomes rotten. We need to determine the minimum number of minutes until all oranges are rotten, or return -1 if it's impossible.

Input/output and constraints:

• Input: m × n grid of integers (0, 1, or 2)
• Output: Integer representing minimum minutes to rot all oranges, or -1 if impossible
• Constraints: Grid dimensions up to 10×10 (assuming typical FAANG constraints)
• Assumption: Grid is valid and contains only 0, 1, or 2 values

Key insights:

• This is fundamentally a multi-source BFS problem where all initially rotten oranges act as starting points
• The "time" is measured by BFS levels, with each level representing one minute
• If any fresh oranges remain after BFS completes, return -1
• The problem has a hidden structure where we're looking for the maximum distance from any fresh orange to its nearest rotten orange

Data shape: 2D grid with discrete states, where we're looking for connected components and propagation patterns.

2. Pattern Recognition

Most likely pattern: Multi-source BFS (Breadth-First Search) / Grid traversal with time-based propagation

Wording that signals the pattern:

• "rotting oranges spread to adjacent fresh oranges" - This indicates a propagation process where each step affects neighboring cells
• "each minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten" - This clearly describes a time-based BFS traversal where the "time" is the BFS level
• "return the minimum number of minutes" - This asks for the maximum time needed, which is a classic BFS level-tracking problem

Why this fits that pattern: This is fundamentally about computing the maximum time for a process to reach all cells in a grid. The rotting process spreads simultaneously from multiple starting points (all initially rotten oranges) to adjacent fresh oranges, just like how BFS explores all nodes at distance k before moving to distance k+1. The key insight is that we're measuring the time for a "wave" of rotting to reach every fresh orange, which is exactly what BFS with level tracking accomplishes.

Core insight: Instead of thinking about individual oranges rotting, think of this as a multi-source flooding process where all rotten oranges simultaneously spread to their neighbors. The minimum time is the maximum distance from any fresh orange to the nearest rotten source, which can be efficiently computed using BFS level tracking.

The problem exhibits a clear "multi-source propagation" pattern where we start from multiple sources and compute the maximum time to reach all targets, making BFS with level tracking the natural algorithmic choice.

3. Approach Evolution

My first instinct is to think about this as a multi-source BFS problem because all the rotten oranges start rotting simultaneously. But that's O(n²) in worst case if we have to check every cell for each rotten orange, which is inefficient. Let me think about how to optimize this.

I notice that if I maintain a queue of all currently rotten oranges and process them level by level, I can reduce it to O(n) time where n is the total number of cells. The key insight is that we can process all the oranges that are currently rotten in one time step, then add their neighbors to the queue for the next time step.

Let me think about this more carefully. We want to find the minimum time for all oranges to rot, so we need to simulate the rotting process. The most efficient approach is to use multi-source BFS where all initially rotten oranges are processed simultaneously.

The core invariant that must hold is that at any time during BFS, we only process oranges that were already rotten at the previous time step. This ensures we're simulating the rotting process correctly, where all oranges that can rot in parallel do so simultaneously.

The approach is:

1. First, identify all initially rotten oranges and add them to a queue
2. Keep track of fresh oranges count
3. Process the queue level by level (time steps)
4. For each rotten orange, check its 4 neighbors
5. If neighbor is fresh, make it rotten and add to queue for next time step
6. Continue until no more oranges can rot
7. Return the time if all fresh oranges rotted, otherwise -1

This is O(m×n) time where m and n are grid dimensions because we visit each cell at most once, and O(m×n) space for the queue in worst case. This is optimal since we must examine each cell at least once to determine if all oranges can rot.

The key optimization is using multi-source BFS instead of processing each rotten orange individually - this reduces redundant work and gives us the correct time simulation.

4. Data Structure Choice

For this rotting oranges problem, I need to carefully select data structures that support efficient traversal and state tracking.

Primary Data Structures:

1. Queue (BFS) - The most critical data structure for this problem is a queue to implement breadth-first search. This enables me to process oranges level by level, simulating the rotting process where all initially rotten oranges spread simultaneously to their adjacent fresh oranges in each time unit.

2. 2D Grid (int[][]) - The input grid itself serves as the primary data structure to represent the state of oranges. I'll use it to track:

   • Fresh oranges (1)
   • Rotten oranges (2)
   • Empty cells (0)

3. Set or HashSet - I could use a set to track visited cells to avoid reprocessing, but since I'm modifying the grid in-place and can distinguish between fresh (1) and rotten (2) states, I don't strictly need a separate visited set.

Why These Choices:

The queue is essential because this is fundamentally a multi-source BFS problem where multiple oranges rot simultaneously and spread to neighbors at the same time. Using a queue ensures I process all currently rotten oranges before moving to the next time step.

The 2D grid is ideal because:

• It's already provided as input and represents the problem state clearly
• I can use it to track the rotting process in-place without additional space for a separate state tracking array
• It allows O(1) access to any cell's status

Space Considerations:

The queue can grow up to the size of the grid in worst case (when all oranges are initially rotten), so space complexity for queue is O(m×n). The grid itself is part of the input and doesn't contribute to auxiliary space.

Alternative Considerations:

I could use a separate boolean visited array, but that would add O(m×n) space and is unnecessary since the grid state itself provides the necessary tracking information. The in-place modification of grid values (1→2) is clean and efficient for this particular problem.

The queue approach elegantly handles the time dimension - each BFS level represents one unit of time, making it a natural fit for this temporal propagation problem.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works:

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

Step 1: Initialize queue with all initially rotten oranges

• Queue: [(0,0), (0,1), (0,2)]
• Fresh count: 4

Step 2: Process queue level by level (BFS style)

• Time = 0, Queue size = 3
• Process (0,0): Add neighbors (1,0) to queue if fresh
• Process (0,1): Add neighbors (1,1) to queue if fresh
• Process (0,2): Add neighbors (1,2) to queue if fresh
• Queue: [(1,0), (1,1), (1,2)]
• Fresh count: 1

Step 3: Continue BFS

• Time = 1, Queue size = 3
• Process (1,0): Add neighbors (2,0) to queue if fresh
• Process (1,1): No new neighbors (all visited/rotten)
• Process (1,2): Add neighbor (2,2) to queue if fresh
• Queue: [(2,0), (2,2)]
• Fresh count: 0

Step 4: Final processing

• Time = 2, Queue size = 2
• Process (2,0): No new neighbors
• Process (2,2): No new neighbors
• Queue: [] (empty)

Step 5: Final check

• Fresh count = 0, so return time = 2

The algorithm correctly identifies that all oranges rot in 2 minutes. The key insight is that we process all currently rotten oranges simultaneously, then their neighbors become rotten in the next time unit - this is exactly BFS behavior.

Edge case handling:

• If fresh count > 0 after processing, return -1 (some oranges never rotted)
• If no initial rotten oranges and fresh count > 0, return -1
• If no fresh oranges initially, return 0

6. Java Solution

import java.util.*;

public class Solution {
    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        
        int rows = grid.length;
        int cols = grid[0].length();
        
        // Directions for adjacent cells (up, down, left, right)
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // Queue to store positions of rotten oranges
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        
        // Initialize queue with all rotten oranges and count fresh oranges
        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});
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }
        
        // If no fresh oranges initially, return 0
        if (freshCount == 0) {
            return 0;
        }
        
        int minutes = 0;
        
        // BFS to rot all fresh oranges
        while (!queue.isEmpty()) {
            int size = queue.size();
            
            // Process all currently rotten oranges at this time step
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int row = current[0];
                int col = current[1];
                
                // Check all 4 adjacent cells
                for (int[] dir : directions) {
                    int newRow = row + dir[0];
                    int newCol = col + dir[1];
                    
                    // Check if adjacent cell is valid and contains a fresh orange
                    if (newRow >= 0 && newRow < rows && 
                        newCol >= 0 && newCol < cols && 
                        grid[newRow][newCol] == 1) {
                        
                        // Rot the fresh orange
                        grid[newRow][newCol] = 2;
                        queue.offer(new int[]{newRow, newCol});
                        freshCount--;
                    }
                }
            }
            
            // Increment time only if there were any oranges that rotted in this step
            if (!queue.isEmpty()) {
                minutes++;
            }
        }
        
        // If there are still fresh oranges left, return -1
        return freshCount == 0 ? minutes : -1;
    }
}

This solution uses a BFS approach to simulate the rotting process. We start by identifying all initially rotten oranges and count fresh oranges. Then we process the grid level by level using BFS, where each level represents one minute passing. For each fresh orange adjacent to a rotten one, we rot it and add it to our processing queue. The time complexity is tracked by counting how many levels of BFS we need to process, and we return -1 if any fresh oranges remain after processing.

7. Complexity Analysis

Time Complexity: O(m × n)

The algorithm processes each cell in the grid at most once. The BFS traversal visits each fresh orange exactly once when it becomes rotten, and each cell is enqueued and dequeued at most once. Since we have at most m × n cells, and each operation (enqueue/dequeue/processing) takes O(1) time, the overall time complexity is O(m × n).

Space Complexity: O(m × n)

The space complexity comes from two sources:

1. The queue used for BFS traversal, which in the worst case can contain all cells in the grid (when all oranges are initially rotten or when the grid is filled with fresh oranges). This gives O(m × n) space.
2. The visited set, which in the worst case can also contain all cells, giving another O(m × n) space.

However, since we're modifying the input grid in-place to mark visited cells (by changing 1s to 2s), we can reduce the auxiliary space usage. But for clarity and correctness in our implementation, we maintain the visited set, which results in O(m × n) space complexity.

Why These Bounds Are Correct:

The bounds are tight because:

• We must examine every cell at least once to determine if all fresh oranges can rot
• The BFS ensures we process cells in order of their rotting time, avoiding redundant processing
• Each cell is processed exactly once due to the visited tracking mechanism

Optimality:

This solution is optimal for the given constraints. Since we must examine every cell at least once to determine if all oranges can rot, O(m × n) time complexity is the theoretical lower bound. Our solution achieves this bound with a single pass through the grid and a BFS traversal, making it near-optimal in both time and space.

The solution is optimal because:

1. It's impossible to solve this problem faster than O(m × n) time since we must inspect each cell
2. It uses the minimum necessary space to track visited cells and maintain BFS queue structure
3. The algorithm avoids redundant operations through proper state management

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty grid: An empty 0x0 or 0xN or Nx0 grid should return 0 minutes (no oranges to rot).
• Single cell grid: A 1x1 grid with value 0 (fresh), 1 (rotten), or 2 (empty) must be handled correctly.
• Single fresh orange: Grid with only one fresh orange should return -1 since it can never rot.

Duplicate Values and Repeated States

• Multiple rotten oranges: When multiple oranges start rotting simultaneously, we must ensure they don't interfere with each other's propagation timing.
• Repeated state tracking: If we don't properly track visited cells, we might count the same orange multiple times in our BFS.

Boundary Conditions

• Border oranges: Oranges at grid edges (first/last row or column) must be handled correctly to avoid index out of bounds errors.
• Mixed states: Grid with a mix of fresh, rotten, and empty cells must be processed without confusion.

Common Implementation Mistakes

• Incorrect queue initialization: Adding all rotten oranges to the queue at once without proper timestamp tracking can lead to incorrect time calculations.
• Not handling the case where no fresh oranges exist: If all oranges are already rotten or empty, we should return 0 instead of -1.
• Failing to handle the case where fresh oranges are unreachable: If a fresh orange is completely surrounded by empty cells or other fresh oranges, it should return -1.
• Incorrect time tracking: Using a global time variable instead of tracking the maximum time across all oranges can lead to wrong results.

Implementation-specific Issues

• Queue vs List confusion: Using a list instead of a proper queue structure can lead to incorrect BFS order and timing.
• Integer overflow: While not likely in this problem, for very large grids, ensure time tracking doesn't overflow.
• Array bounds: Not checking array bounds when accessing neighboring cells can cause runtime exceptions.

The solution must carefully handle all these edge cases to ensure correctness across the full spectrum of valid inputs.

9. Alternative Approaches

There are several alternative approaches to solving the rotting oranges problem, each with different trade-offs:

BFS with Separate Queues: Instead of using a single queue, we could maintain separate queues for fresh and rotten oranges. This approach would require tracking the current level of BFS traversal separately, but it's essentially the same complexity as our solution.

Multi-source BFS with Level Tracking: We could modify our approach to track the exact level (minute) when each orange rots. This would involve storing (row, col, minute) triplets in our queue, which adds a small constant factor to space complexity but makes the logic more explicit.

Simulation-Based Approach: We could simulate the rotting process step-by-step, using a boolean grid to track which oranges are fresh and which are rotten. At each step, we would check all currently rotten oranges to see if they can rot adjacent fresh ones. This approach is more intuitive but requires more complex state management and potentially more iterations.

DFS-Based Solution: While less natural for this problem, we could use DFS to find the maximum time needed to rot all oranges. However, this approach is more complex to implement correctly and doesn't provide better complexity bounds than BFS.

Time-Indexed Tracking: We could maintain a map or array that tracks which oranges rot at each time step. This would allow us to easily determine the maximum time, but it adds complexity in tracking which oranges are fresh at any given moment.

The chosen BFS approach is preferred because it's naturally suited to finding the minimum time for all oranges to rot, and it's both time and space optimal. The alternatives either add unnecessary complexity or don't improve on the fundamental O(m×n) bounds.

// Alternative: Multi-source BFS with level tracking
public int orangesRottingAlternative(int[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
        return -1;
    }
    
    int rows = grid.length;
    int cols = grid[0].length();
    Queue<int[]> queue = new LinkedList<>();
    int freshCount = 0;
    
    // Initialize queue with all rotten oranges and count fresh ones
    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, 0}); // {row, col, time}
            } else if (grid[i][j] == 1) {
                freshCount++;
            }
        }
    }
    
    if (freshCount == 0) return 0;
    
    int maxTime = 0;
    int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    while (!queue.isEmpty()) {
        int[] current = queue.poll();
        int row = current[0];
        int col = current[1];
        int time = current[2];
        
        maxTime = Math.max(maxTime, time);
        
        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];
            
            if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == 1) {
                grid[newRow][newCol] = 2; // Mark as rotten
                queue.offer(new int[]{newRow, newCol, time + 1});
                freshCount--;
            }
        }
    }
    
    return freshCount == 0 ? maxTime : -1;
}

10. Test Cases

// Test case 1: Basic case with some oranges rotting
int[][] grid1 = {{2,1,1},{1,1,0},{0,1,1}};
// Expected: 4

// Test case 2: All oranges already rotten
int[][] grid2 = {{0,1,1},{1,1,0},{0,1,1}};
// Expected: 0

// Test case 3: Impossible to rot all oranges
int[][] grid3 = {{0,1,1},{1,1,0},{0,1,1}};
// Expected: -1

// Test case 4: Empty grid
int[][] grid4 = {{0,0,0},{0,0,0},{0,0,0}};
// Expected: 0

// Test case 5: Single cell - fresh
int[][] grid5 = {{1}};
// Expected: -1

// Test case 6: Single cell - rotten
int[][] grid6 = {{2}};
// Expected: 0

// Test case 7: Single cell - empty
int[][] grid7 = {{0}};
// Expected: 0

// Test case 8: Large grid with multiple fresh oranges
int[][] grid8 = {{2,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,1},{1,1,1,1,2}};
// Expected: 4

The test cases cover:

• Normal case with mixed fresh/rotten/orange-free cells
• Edge case where all oranges are already rotten
• Impossible case where fresh oranges are isolated by empty cells
• Empty grid with no oranges at all
• Single cell edge cases (fresh, rotten, empty)
• Larger grid to verify multi-step propagation works correctly

Each test case validates different aspects of the algorithm's behavior including time propagation, impossible scenarios, and boundary conditions.

11. Final Summary

The core insight is to model this as a multi-source BFS problem where all initially rotten oranges act as starting points for simultaneous propagation. By tracking the maximum time needed to rot all reachable fresh oranges, we efficiently compute the minimum time required for complete decay.

This solution works because it leverages the fundamental property that in a grid-based BFS, the first time we reach any cell is optimal - there's no way to reach that cell faster than the earliest BFS step that discovers it. The algorithm naturally handles the simultaneous spread from all initial rotting points, ensuring we find the true minimum time.

The approach is optimal with O(m×n) time and space complexity, where m and n are grid dimensions. It's efficient because it avoids redundant computations by processing cells in layers of increasing time, and uses a queue-based BFS to ensure each cell is processed exactly once. The solution elegantly handles edge cases like empty grids, no fresh oranges, or unreachable fresh oranges through careful initialization and termination conditions.