Rotting Oranges

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

Naive Approach

A brute-force approach would involve iterating through the grid at each minute, identifying all rotten oranges, and then checking their neighbors to rot any fresh oranges. This process continues until no more fresh oranges can be rotten.

1. Iterate: Loop through the grid.
2. Identify Rotten: Find all rotten oranges (value 2).
3. Check Neighbors: For each rotten orange, check its 4-directional neighbors.
4. Rot Fresh Oranges: If a neighbor is a fresh orange (value 1), mark it as rotten.
5. Repeat: Continue this process until no more fresh oranges are available to rot.

This approach is inefficient because it rescans the entire grid at each step, even if only a few oranges have been freshly rotten.

Time Complexity: O(T * m * n), where T is the number of minutes and m * n is the size of the grid. In the worst case, T could be proportional to m * n.

Space Complexity: O(m * n) in the worst case, if you need to maintain a copy of the grid to track changes.

Optimal Solution

A better approach involves using Breadth-First Search (BFS).

1. Initialization:
   • Find all initial rotten oranges and add their coordinates to a queue.
   • Count the number of fresh oranges.
2. BFS:
   • While the queue is not empty:
     • Process all oranges rotten at the current minute.
     • For each rotten orange, check its 4-directional neighbors.
     • If a neighbor is fresh, rot it and add its coordinates to the queue.
     • Increment the minute count.
3. Check Fresh Oranges:
   • After the BFS, if there are still fresh oranges, return -1. Otherwise, return the minute count.

This approach optimizes the process by exploring oranges layer by layer, ensuring that oranges rot in the correct order.

Big O Time Complexity: O(m * n), where m * n is the size of the grid, as each cell is visited at most a constant number of times.

Big O Space Complexity: O(m * n) in the worst-case scenario, where the queue might contain all the cells in the grid.

Edge Cases

• Empty Grid: If the grid is empty, return 0.
• No Fresh Oranges Initially: If there are no fresh oranges initially, return 0.
• No Rotten Oranges Initially: If there are no rotten oranges initially but there are fresh oranges, it's impossible to rot all oranges, so return -1.
• Oranges Isolated: If some fresh oranges are isolated and cannot be reached by rotten oranges, return -1.

Code Example (Python)

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_oranges = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))  # (row, col, time)
            elif grid[r][c] == 1:
                fresh_oranges += 1

    if not queue and fresh_oranges > 0:
        return -1

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

    while queue:
        r, c, time = queue.popleft()
        minutes = time

        for dr, dc in directions:
            new_r, new_c = r + dr, c + dc

            if (0 <= new_r < rows and 0 <= new_c < cols and grid[new_r][new_c] == 1):
                grid[new_r][new_c] = 2  # Rot the orange
                fresh_oranges -= 1
                queue.append((new_r, new_c, time + 1))

    if fresh_oranges > 0:
        return -1
    else:
        return minutes