Rotting Oranges medium

Problem Statement

You are given an m x n grid representing a garden made of oranges. Each cell has one of three values:

• 0: empty cell
• 1: orange that is fresh
• 2: orange that is rotten

Every minute, any fresh orange that is 4-directionally adjacent (up, down, left, or right) 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.

Example 1

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

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1

Steps

1. Initialization:

   • Create a queue to store the coordinates of initially rotten oranges.
   • Count the total number of fresh oranges. We'll use this to check if all oranges have eventually rotted.
   • Initialize a variable minutes to 0 (to track time).

2. Breadth-First Search (BFS):

   • While the queue is not empty:
     • Get the size of the queue (number of oranges to process in the current minute).
     • Iterate through the oranges in the current queue:
       • For each rotten orange at (row, col), explore its four neighbors:
         • If a neighbor is a fresh orange (value 1):
           • Change its value to 2 (rotten).
           • Add its coordinates to the queue.
           • Decrement the count of fresh oranges.
     • Increment minutes (one minute has passed).

3. Check for Fresh Oranges:

   • If the count of fresh oranges is 0, it means all oranges have rotted, and we return minutes.
   • If the queue becomes empty before all fresh oranges have rotted, it means some oranges remain fresh and cannot be reached; return -1.

Explanation

The problem can be efficiently solved using Breadth-First Search (BFS). BFS guarantees that we process oranges in the order they become rotten, ensuring we find the minimum time. We use a queue to maintain the order of processing. Each iteration of the outer while loop represents one minute of time elapsing. The inner loop processes all the oranges that became rotten in the previous minute. The count of fresh oranges helps us efficiently determine if all oranges have rotted.

Code

from collections import deque

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

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

    # No fresh oranges, return 0
    if fresh_count == 0:
        return 0

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

    while queue:
        size = len(queue)
        for _ in range(size):
            row, col = queue.popleft()
            for dr, dc in directions:
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    queue.append((nr, nc))
                    fresh_count -= 1
        minutes += 1

    # Check if all fresh oranges have rotted
    return minutes if fresh_count == 0 else -1

Complexity

• Time Complexity: O(M * N), where M and N are the dimensions of the grid. We visit each cell at most once.
• Space Complexity: O(M * N) in the worst case, where the queue could hold all the cells in the grid if all oranges are initially rotten.