Rotting Oranges: Multiple Solutions and Complexity Analysis

Introduction to the Rotting Oranges Problem

The "Rotting Oranges" problem is a classic algorithmic challenge frequently found on coding interview platforms like LeetCode. It presents a grid-based scenario where you must determine the minimum time required for all oranges in a grid to rot, given that rotten oranges can infect adjacent fresh oranges every minute. This problem is an excellent test of a developer's understanding of graph traversal techniques, specifically Breadth-First Search (BFS).

What is the Rotting Oranges Problem?

You are given an m x n grid where each cell represents one of three states:

0: An empty cell.
1: A fresh orange.
2: A rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent (up, down, left, right) to a rotten orange becomes rotten. Your task is to return the minimum number of minutes that must elapse until no fresh orange remains. If it is impossible to rot all the fresh oranges (i.e., some are completely isolated), you must return -1.

Why It Matters

This problem matters because it simulates real-world propagation scenarios, such as the spread of a virus, network packet routing, or fire spreading through a grid. Solving it requires recognizing that the grid is essentially an unweighted graph, and finding the minimum time to reach all nodes is a shortest-path problem. Multi-source BFS is the optimal strategy here, as all initially rotten oranges act as simultaneous starting points for the propagation.

Approaches to Solve the Problem

Solution 1: Multi-Source Breadth-First Search (Level-Order Traversal)

The most intuitive and efficient way to solve this problem is by using a queue to implement a multi-source BFS. First, we scan the grid to find all initially rotten oranges and enqueue their positions. We also count the total number of fresh oranges. Then, we process the queue level by level. Each level in the BFS corresponds to one minute of time passing. When we pop an orange from the queue, we check its four neighbors. If a neighbor is a fresh orange, we rot it, decrement the fresh orange count, and add it to the queue for the next minute's propagation.

from collections import deque

def orangesRotting(grid):
    if not grid or not grid[0]:
        return -1
    
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0
    
    # Step 1: Initialize queue with all rotten oranges and count fresh oranges
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh_count += 1
                
    # If there are no fresh oranges, it takes 0 minutes
    if fresh_count == 0:
        return 0
        
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    minutes_passed = 0
    
    # Step 2: Perform BFS
    while queue:
        # Process all oranges that are rotting at the current minute
        current_level_size = len(queue)
        has_rotted_this_minute = False
        
        for _ in range(current_level_size):
            r, c = queue.popleft()
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                
                # If adjacent cell is within bounds and has a fresh orange
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2  # Rot the fresh orange
                    fresh_count -= 1
                    queue.append((nr, nc))
                    has_rotted_this_minute = True
                    
        # Only increment time if we actually rotted new oranges
        if has_rotted_this_minute:
            minutes_passed += 1
            
    # Step 3: Check if any fresh oranges remain unreachable
    return minutes_passed if fresh_count == 0 else -1

Complexity Analysis of Solution 1

Time Complexity: O(m * n). We traverse the entire grid initially to find rotten and fresh oranges, which takes O(m * n). The BFS also visits each cell at most once, resulting in an overall time complexity of O(m * n).

Space Complexity: O(m * n). In the worst-case scenario (e.g., all oranges are rotten initially), the queue will hold all m * n cells simultaneously.

Solution 2: BFS with a Distance Matrix

An alternative approach involves using a separate 2D array to keep track of the time (distance) it takes for each orange to rot, rather than processing the queue level by level. We initialize the distance matrix with infinity (or a very large number), set the distance to 0 for initially rotten oranges, and use the queue to propagate the time. This approach is slightly more space-intensive but can be easier to adapt for weighted graph variations.

from collections import deque
import math

def orangesRottingDistance(grid):
    if not grid or not grid[0]:
        return -1
        
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    dist = [[math.inf] * cols for _ in range(rows)]
    fresh_count = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
                dist[r][c] = 0
            elif grid[r][c] == 1:
                fresh_count += 1
                
    if fresh_count == 0:
        return 0
        
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    max_time = 0
    
    while queue:
        r, c = queue.popleft()
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                # Only update if the new distance is shorter
                if dist[r][c] + 1 < dist[nr][nc]:
                    dist[nr][nc] = dist[r][c] + 1
                    queue.append((nr, nc))
                    max_time = max(max_time, dist[nr][nc])
                    fresh_count -= 1 # Decrement to track if we reached all
                    
    # If max_time remained 0 but we had fresh oranges, it means they were unreachable
    # We check fresh_count to ensure all were reached
    return max_time if fresh_count == 0 else -1

Complexity Analysis of Solution 2

Time Complexity: O(m * n). Similar to the first solution, each cell is processed a constant number of times.

Space Complexity: O(m * n). However, this solution uses an additional m x n matrix for distances, making it slightly less optimal in space than Solution 1, which modifies the grid in-place.

Best Practices and Edge Cases

When implementing a solution for the Rotting Oranges problem, keep the following best practices and edge cases in mind:

Handle Empty Grids: Always check if the grid or its rows are empty at the very beginning to avoid index out-of-bounds errors.
Zero Fresh Oranges: If the grid contains only rotten oranges and empty cells (no fresh oranges), the algorithm should immediately return 0 minutes, as no time is needed for rotting.
Unreachable Fresh Oranges: Ensure your algorithm correctly identifies scenarios where fresh oranges are blocked by empty cells. If the final count of fresh oranges is greater than zero, return -1.
In-Place Modification: To optimize space, modify the input grid directly (e.g., changing a 1 to a 2) to mark it as visited and rotten, avoiding the need for a separate visited matrix.
Use Deque: Always use a double-ended queue (deque in Python) for BFS implementations to ensure O(1) time complexity for pop and append operations.

Conclusion

The Rotting Oranges problem is a quintessential example of how matrix traversal problems can be mapped to graph theory. By recognizing the grid as an unweighted graph and the initially rotten oranges as multiple starting points, developers can leverage multi-source Breadth-First Search to find the optimal solution efficiently. Whether you choose a level-order traversal or a distance-matrix approach, understanding the time and space complexities ensures you can scale your solution effectively. Mastering this problem builds a strong foundation for tackling more complex propagation and shortest-path challenges in software development.