Problem Statement

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.

Additional information

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

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

Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]

Output: 0

Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Brute Force (Grid Simulation)

Intuition

A naive way to solve this is to simulate the rotting process exactly as time passes, minute by minute.

At each minute, we scan the entire grid. If we find a rotten orange (2), we look at its 4 neighbors. If any neighbor is a fresh orange (1), we mark it to become rotten. However, we cannot turn it into a 2 immediately, because our loop might reach that new 2 later in the same minute and accidentally spread the rot twice!

To fix this, we can turn newly rotting oranges into a temporary value (like 3). At the end of the minute, we scan the grid again to turn all 3s into 2s. If a full minute passes and absolutely zero oranges turn from 1 to 3, the rotting process has completely halted. We then do one final scan to see if any 1s are left over.

Algorithm

1. Store the dimensions rows and cols.
2. Initialize a minutes counter to 0.
3. Start an infinite while True loop.
4. Track a boolean rotted_this_minute set to False.
5. Iterate through every cell r, c in the grid.
6. If grid[r][c] == 2, check its up, down, left, and right neighbors.
7. If a neighbor is 1, change it to 3 and set rotted_this_minute = True.
8. If rotted_this_minute is False, break out of the infinite loop (the spreading has stopped).
9. Iterate through the grid again to change all 3s into 2s (finalizing the rot for this minute).
10. Increment the minutes counter.
11. After the loop breaks, scan the grid one last time. If any 1 remains, return -1. Otherwise, return minutes.

def oranges_rotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    minutes = 0
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    
    while True:
        rotted_this_minute = False
        
        # Step 1: Mark newly rotting oranges as 3
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    for dr, dc in directions:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                            grid[nr][nc] = 3
                            rotted_this_minute = True
                            
        # Step 2: If nothing changed, the simulation is over
        if not rotted_this_minute:
            break
            
        # Step 3: Finalize the rot (turn 3s into 2s) for the next minute
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 3:
                    grid[r][c] = 2
                    
        minutes += 1
        
    # Final check for unreachable fresh oranges
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                return -1
                
    return minutes

Time & Space Complexity

• Time complexity: O((M * N)^2)

• Reason: In the worst-case scenario (e.g., a long snake-like zig-zag pattern of fresh oranges with one rotten orange at the very end), exactly one orange rots per minute. This requires us to scan the entire M * N grid M * N times, resulting in quadratic grid-time.

• Space complexity: O(1)

• Reason: We are modifying the grid entirely in-place, requiring no extra auxiliary memory structures.

Multi-Source Breadth-First Search (BFS) - Optimal

Intuition

Scanning the entire grid every single minute does a massive amount of redundant work. Once a rotten orange has infected its neighbors, it can never infect anything else. We only ever need to look at the newly rotten oranges!

This is the perfect scenario for an iterative Breadth-First Search (BFS). But since there can be multiple rotten oranges at minute 0, we can't just start from one. We need a Multi-Source BFS.

We do one initial scan of the grid to count all the fresh oranges (so we know when we are done) and to put all the currently rotten oranges into a Queue. Then, we process the queue level by level (minute by minute), popping rotten oranges and appending newly infected oranges.

Algorithm

1. Initialize a deque (queue).
2. Initialize fresh_count = 0 and minutes = 0.
3. Iterate through the grid. If a cell is 1, increment fresh_count. If a cell is 2, append its coordinates (r, c) to the queue.
4. While the queue is not empty and fresh_count > 0:

• Get the number of oranges currently in the queue (level_size = len(queue)).
• Loop level_size times to process only the oranges that rotted in the previous minute.
• Pop the orange, check its 4 neighbors.
• If a neighbor is 1, make it 2, decrement fresh_count, and add it to the queue.
• After the level_size loop finishes, increment minutes by 1.

5. If fresh_count == 0, return minutes. Otherwise, return -1.

def oranges_rotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    q = deque()
    fresh_count = 0
    
    # Initial scan to find all rotten oranges and count fresh ones
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh_count += 1
                
    minutes = 0
    directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    
    # BFS level-order traversal
    while q and fresh_count > 0:
        level_size = len(q)
        
        for _ in range(level_size):
            r, c = q.popleft()
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                # If a neighbor is fresh, rot it
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh_count -= 1
                    q.append((nr, nc))
                    
        minutes += 1
        
    return minutes if fresh_count == 0 else -1

Time & Space Complexity

• Time complexity: O(M * N)

• Reason: We scan the grid once to initialize the queue, and then the BFS processes each cell at most once. The total operations scale linearly with the total number of cells in the grid.

• Space complexity: O(M * N)

• Reason: In the worst-case scenario (e.g., all oranges are rotten at the start), the queue will hold M * N coordinates.