Rotting Oranges

December 26, 2023

Problem #

In a given grid, each cell can have one of three values: 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange that is adjacent to a rotten orange becomes rotten. Find the minimum number of minutes that must elapse until no cell has a fresh orange.

Solution #

To solve this problem, we can use the Breadth-First Search (BFS) algorithm. The idea is to iteratively spread the rot from the rotten oranges to the adjacent fresh oranges and track the time taken for all fresh oranges to become rotten. If it’s not possible to rot all the fresh oranges (due to isolation), we return -1. Here’s a Python implementation:

from collections import deque

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    fresh_count = 0
    queue = deque()

    # Initialize the 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

    # Directions for adjacent cells (up, down, left, right)
    directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
    minutes = 0

    # BFS
    while queue and fresh_count > 0:
        minutes += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    fresh_count -= 1
                    queue.append((nx, ny))

    return minutes if fresh_count == 0 else -1

# Example Usage
grid = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1]
]
print("Minimum minutes to rot all oranges:", orangesRotting(grid))

In this code:

• We first iterate through the grid to find the initial positions of rotten oranges and count the number of fresh oranges.
• These positions are added to a queue for BFS.
• We then perform BFS. In each round (or minute), we process all the rotten oranges in the queue and try to rot the adjacent fresh oranges.
• Each time a fresh orange rots, we decrease the count of fresh oranges.
• After each round, we increment the minutes.
• The process continues until there are no more fresh oranges or there are no more oranges that can be rotten (i.e., the queue is empty but there are still fresh oranges left).
• If there are no more fresh oranges, we return the minutes taken; otherwise, we return -1, indicating it’s impossible to rot all oranges.

This algorithm efficiently solves the problem with a time complexity of O(N*M), where N and M are the number of rows and columns in the grid, respectively.