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 it is impossible, return -1.

For example, consider the following grid:

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

In this case, the function should return 4 because it takes 4 minutes for all the fresh oranges to rot.

As another example, consider the following grid:

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

In this case, the function should return -1 because the orange in the bottom left will never rot.

Here's how the rotting process would proceed in the first example:

Initial state:

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

After 1 minute:

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

After 2 minutes:

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

After 3 minutes:

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

After 4 minutes:

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

All fresh oranges are now rotten after 4 minutes. Write a function to solve this problem efficiently. Consider edge cases such as an empty grid or a grid with no fresh oranges initially.

Rotting Oranges

Problem Description

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 it is impossible, return -1.

Brute Force Solution

A brute force approach would involve iterating through the grid at each minute, identifying fresh oranges adjacent to rotten oranges, and marking them as rotten. We would continue this process until no more oranges can rot or until a maximum time limit is reached. This approach is inefficient because it involves redundant checks and updates at each minute.

Optimal Solution

The optimal solution uses Breadth-First Search (BFS) to simulate the rotting process. Here's the algorithm:

1. Initialization:

   • Find all rotten oranges and add their coordinates to a queue.
   • Count the number of fresh oranges.
   • Initialize the time (minutes) to 0.

2. BFS Iteration:

   • While the queue is not empty:
     • Process all oranges that rotted at the current minute.
     • For each rotten orange, check its 4-directionally adjacent cells.
     • If a fresh orange is found, rot it (change its value to 2), decrement the fresh orange count, and add its coordinates to the queue.
     • Increment the time (minutes) after processing all oranges at the current level.

3. Check for Unrotted Oranges:

   • If the fresh orange count is still greater than 0 after the BFS iteration, return -1 (impossible to rot all oranges).
   • Otherwise, return the time (minutes).

from collections import deque

def rotting_oranges(grid):
    if not grid:
        return -1

    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_oranges = 0
    
    # Initialize queue with 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_oranges += 1

    minutes = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while queue:
        # Process all oranges that rotted at the current minute
        for _ in range(len(queue)):
            row, col = queue.popleft()

            # Check adjacent cells
            for dr, dc in directions:
                new_row, new_col = row + dr, col + dc

                if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == 1:
                    # Rot the fresh orange
                    grid[new_row][new_col] = 2
                    fresh_oranges -= 1
                    queue.append((new_row, new_col))

        # Increment minutes after processing current level
        minutes += 1

    # If any fresh oranges remain, it's impossible to rot them all
    if fresh_oranges > 0:
        return -1

    # Return the time taken to rot all oranges, subtract 1 because of the last increment
    return minutes - 1

# Example Usage
grid1 = [[2,1,1],[1,1,0],[0,1,1]]
print(rotting_oranges(grid1))  # Output: 4

grid2 = [[2,1,1],[0,1,1],[1,0,1]]
print(rotting_oranges(grid2))  # Output: -1

grid3 = [[0,2]]
print(rotting_oranges(grid3)) # Output: 0

grid4 = [[0]]
print(rotting_oranges(grid4)) # Output: 0

grid5 = [[1]]
print(rotting_oranges(grid5)) # Output: -1

Big(O) Runtime Analysis

The time complexity of the optimal solution is O(m * n), where m is the number of rows and n is the number of columns in the grid.

• We iterate through the entire grid once to initialize the queue and count fresh oranges, which takes O(m * n) time.
• In the worst case, each cell might be added to the queue once, and for each cell, we check its 4 neighbors. So, the BFS iteration takes O(m * n) time in the worst case.

Therefore, the overall time complexity is O(m * n) + O(m * n) which simplifies to O(m * n).

Big(O) Space Usage Analysis

The space complexity of the optimal solution is O(m * n) in the worst case.

• The queue can contain all the cells of the grid if all oranges are initially rotten. Therefore, the space required for the queue is O(m * n).
• We only use a few extra variables to store the number of fresh oranges and the time, which take constant space O(1).

Thus, the overall space complexity is dominated by the queue, which is O(m * n).

Edge Cases

1. Empty Grid: If the input grid is empty (either 0 rows or 0 columns), the function should return -1, as there are no oranges to rot.
2. No Rotten Oranges: If there are no rotten oranges initially, and there are fresh oranges, the function should return -1 because no oranges will ever rot.
3. No Fresh Oranges: If there are no fresh oranges initially, the function should return 0 because no time is needed for rotting.
4. Only Rotten Oranges: If all oranges are initially rotten, the function should return 0, as no time is needed.
5. Single Cell Grid: The grid may contain only one cell, which could be empty, fresh, or rotten. The function should handle these cases correctly.
6. Disconnected Fresh Oranges: If some fresh oranges are not reachable from any rotten orange, the function should return -1.