Rotten Oranges Problem

Find the minimum time for all oranges to rot using BFS

Language Selection

Choose your preferred programming language

Showing: Python

Rotten Oranges Problem

Problem Statement

You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Input/Output Specifications

  • Input: A 2D grid where 1 <= m, n <= 10 and each cell contains 0, 1, or 2
  • Output: An integer representing the minimum minutes to rot all oranges, or -1 if impossible

Constraints

  • 1 <= m, n <= 10
  • Each cell contains 0, 1, or 2

Examples

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: 
Minute 0: [[2,1,1],[1,1,0],[0,1,1]]
Minute 1: [[2,2,1],[2,1,0],[0,1,1]]
Minute 2: [[2,2,2],[2,2,0],[0,1,1]]
Minute 3: [[2,2,2],[2,2,0],[0,2,1]]
Minute 4: [[2,2,2],[2,2,0],[0,2,2]]

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are no fresh oranges, 0 minutes have passed.

Solution Approaches

Approach 1: Multi-Source BFS - Optimal

Algorithm Explanation:

  1. Find all initially rotten oranges and add them to the queue
  2. Use BFS to spread rot to adjacent fresh oranges
  3. Track the time (minutes) for each level of BFS
  4. Check if all fresh oranges are rotten at the end

Implementation:

Python:

from collections import deque

def orangesRotting(grid):
    """
    Find minimum time for all oranges to rot using multi-source BFS
    Time: O(m * n)
    Space: O(m * n)
    """
    if not grid or not grid[0]:
        return -1
    
    m, n = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0
    
    # Find all initially rotten oranges and count fresh oranges
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                queue.append((i, j, 0))  # (row, col, time)
            elif grid[i][j] == 1:
                fresh_count += 1
    
    # If no fresh oranges, return 0
    if fresh_count == 0:
        return 0
    
    # Directions: up, down, left, right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    max_time = 0
    
    while queue:
        row, col, time = queue.popleft()
        
        # Check all 4 directions
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Check bounds and if cell has fresh orange
            if (0 <= new_row < m and 0 <= new_col < n and 
                grid[new_row][new_col] == 1):
                
                # Make orange rotten
                grid[new_row][new_col] = 2
                fresh_count -= 1
                
                # Add to queue with incremented time
                queue.append((new_row, new_col, time + 1))
                max_time = max(max_time, time + 1)
    
    # Return -1 if fresh oranges remain, otherwise return max time
    return -1 if fresh_count > 0 else max_time

Java:

import java.util.*;

class Solution {
    public int orangesRotting(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return -1;
        }
        
        int m = grid.length;
        int n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int freshCount = 0;
        
        // Find all initially rotten oranges and count fresh oranges
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j, 0}); // {row, col, time}
                } else if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }
        
        // If no fresh oranges, return 0
        if (freshCount == 0) {
            return 0;
        }
        
        // Directions: up, down, left, right
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int maxTime = 0;
        
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int row = current[0];
            int col = current[1];
            int time = current[2];
            
            // Check all 4 directions
            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];
                
                // Check bounds and if cell has fresh orange
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && 
                    grid[newRow][newCol] == 1) {
                    
                    // Make orange rotten
                    grid[newRow][newCol] = 2;
                    freshCount--;
                    
                    // Add to queue with incremented time
                    queue.offer(new int[]{newRow, newCol, time + 1});
                    maxTime = Math.max(maxTime, time + 1);
                }
            }
        }
        
        // Return -1 if fresh oranges remain, otherwise return max time
        return freshCount > 0 ? -1 : maxTime;
    }
}

Complexity Analysis:

  • Time Complexity: O(m * n) - Visit each cell at most once
  • Space Complexity: O(m * n) - Queue can store all cells in worst case

Key Insights

  1. Multi-Source BFS: Start BFS from all initially rotten oranges simultaneously
  2. Time Tracking: Track the time (minutes) for each level of BFS
  3. Fresh Count: Keep track of remaining fresh oranges
  4. Grid Modification: Modify the grid in-place to mark oranges as rotten

Edge Cases

  1. No Fresh Oranges: Return 0 if no fresh oranges exist
  2. Isolated Fresh Oranges: Return -1 if some fresh oranges cannot be reached
  3. Empty Grid: Handle empty or null grid
  4. Single Cell: Handle 1x1 grid
  5. All Rotten: Handle grid with all rotten oranges

Test Cases

def test_orangesRotting():
    # Test case 1
    grid1 = [[2,1,1],[1,1,0],[0,1,1]]
    assert orangesRotting(grid1) == 4
    
    # Test case 2
    grid2 = [[2,1,1],[0,1,1],[1,0,1]]
    assert orangesRotting(grid2) == -1
    
    # Test case 3
    grid3 = [[0,2]]
    assert orangesRotting(grid3) == 0
    
    # Test case 4
    grid4 = [[1,2]]
    assert orangesRotting(grid4) == 1
    
    print("All tests passed!")

test_orangesRotting()

Follow-up Questions

  1. 8-Directional: What if oranges can rot in 8 directions?
  2. Multiple Types: What if there are different types of oranges?
  3. Obstacles: What if there are obstacles that block rotting?
  4. Time Constraints: What if there’s a time limit?
  5. Optimization: How would you optimize for very large grids?

Common Mistakes

  1. Single Source BFS: Starting BFS from only one rotten orange
  2. Time Calculation: Incorrect time tracking in BFS
  3. Fresh Count: Not properly tracking remaining fresh oranges
  4. Boundary Checks: Not checking grid boundaries
  5. Edge Case Handling: Not handling no fresh oranges case

Interview Tips

  1. Start with BFS: Begin with BFS approach
  2. Explain Multi-Source: Describe why multi-source BFS is needed
  3. Discuss Time Tracking: Explain how to track minutes
  4. Handle Edge Cases: Cover all edge cases
  5. Code Carefully: Pay attention to grid bounds and state updates

Concept Explanations

Multi-Source BFS: A BFS variant where we start from multiple sources simultaneously. This is useful when we need to find the shortest distance from any of the sources.

Grid Traversal: The process of visiting cells in a 2D grid, typically using BFS or DFS with directional movements.

State Propagation: The process of spreading a state (like rot) from one cell to adjacent cells over time.

When to Use: Use this pattern when you need to simulate processes that spread over time in a grid, such as infection spread, fire spread, or in this case, orange rotting.