LeetCode Solutions Blog

Rotting Oranges

Number: 1036

Difficulty: Medium

Paid? No

Problem Description

Given an m x n grid where each cell is either empty (0), contains a fresh orange (1), or a rotten orange (2), determine the minimum number of minutes that must elapse until no cell has a fresh orange, knowing that every minute any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. If it is impossible for every fresh orange to rot, return -1.

Key Insights

Use Breadth-First Search (BFS) starting from all initially rotten oranges.
Process the grid level by level, where each level represents one minute.
Keep a count of fresh oranges and decrement it as they become rotten.
If after the BFS there are still fresh oranges, then it is impossible to rot every orange.

Space and Time Complexity

Time Complexity: O(m * n) as every cell is processed at most once. Space Complexity: O(m * n) in the worst case for the queue and auxiliary storage.

Solution

We begin by scanning the grid to locate all rotten oranges and count the fresh ones. These rotten oranges are added to a queue for a BFS. For each minute (BFS level), we process all the current rotten oranges and try to infect their adjacent fresh oranges. If an adjacent cell contains a fresh orange, we mark it rotten, add it to the queue, and decrement our fresh count. We continue this process level by level (minute by minute) until there are no fresh oranges left. If, after processing, there are still fresh oranges remaining, we return -1, indicating that not all oranges can become rotten.

Code Solutions

from collections import deque

def orangesRotting(grid):
    # Dimensions of the grid
    rows, cols = len(grid), len(grid[0])
    # Queue to perform BFS, containing tuples of (row, col)
    rotten_queue = deque()
    fresh_count = 0
    
    # Step 1: Initialize the queue with all initially rotten oranges and count fresh oranges.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                rotten_queue.append((r, c))
            elif grid[r][c] == 1:
                fresh_count += 1
                
    # If there are no fresh oranges, return 0 immediately.
    if fresh_count == 0:
        return 0
    
    minutes_passed = 0
    # Directions for adjacent cells: up, down, left, right.
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    
    # Step 2: BFS to rot adjacent fresh oranges.
    while rotten_queue:
        # Process oranges that are rotten in the current minute.
        for _ in range(len(rotten_queue)):
            x, y = rotten_queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                # Check if the neighbor is inside the grid and is a fresh orange.
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                    # Mark the fresh orange as rotten.
                    grid[nx][ny] = 2
                    fresh_count -= 1
                    # Add the new rotten orange into the queue.
                    rotten_queue.append((nx, ny))
        # Increment minutes after processing one level.
        minutes_passed += 1
    
    # If there are still fresh oranges left, return -1.
    return minutes_passed - 1 if fresh_count == 0 else -1

# Example usage:
# grid = [[2,1,1],[1,1,0],[0,1,1]]
# print(orangesRotting(grid))