Rotting Oranges

Problem

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.

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 0.

Constraints:

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

Solution

Approach: Multi-Source BFS

The key insight is to use BFS starting from all rotten oranges simultaneously, processing them level by level to simulate time passing.

Implementation

from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        queue = deque()
        fresh_count = 0

        # Find all initially rotten oranges and count fresh ones
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j, 0))  # (row, col, time)
                elif grid[i][j] == 1:
                    fresh_count += 1

        # If no fresh oranges, return 0
        if fresh_count == 0:
            return 0

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

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

            for dr, dc in directions:
                nr, nc = r + dr, c + dc

                # Check if neighbor is a fresh orange
                if (0 <= nr < m and 0 <= nc < n and
                    grid[nr][nc] == 1):
                    # Make it rotten
                    grid[nr][nc] = 2
                    fresh_count -= 1
                    queue.append((nr, nc, time + 1))

        # If there are still fresh oranges, return -1
        return minutes if fresh_count == 0 else -1

Alternative Implementation (Level-by-Level)

from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        queue = deque()
        fresh_count = 0

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    fresh_count += 1

        if fresh_count == 0:
            return 0

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

        while queue and fresh_count > 0:
            minutes += 1
            # Process all oranges that rotted in current minute
            for _ in range(len(queue)):
                r, c = queue.popleft()

                for dr, dc in directions:
                    nr, nc = r + dr, c + dc

                    if (0 <= nr < m and 0 <= nc < n and
                        grid[nr][nc] == 1):
                        grid[nr][nc] = 2
                        fresh_count -= 1
                        queue.append((nr, nc))

        return minutes if fresh_count == 0 else -1

Complexity Analysis

Time Complexity: O(m * n), where m and n are grid dimensions. We visit each cell at most once.
Space Complexity: O(m * n) for the queue in worst case (if all cells are rotten).

Key Insights

Multi-Source BFS: Unlike typical BFS from a single source, we start from all rotten oranges simultaneously.
Level-by-Level Processing: Each level of BFS represents one minute passing, making all adjacent fresh oranges rot.
Fresh Orange Tracking: We count fresh oranges at the start and decrement as they rot, allowing us to detect if any remain unreachable.
Time Tracking: Two approaches work:
- Store time with each cell in queue
- Process queue level by level and increment minutes after each level
Early Exit: If there are no fresh oranges initially, we can return 0 immediately.
Impossible Cases: If fresh oranges remain after BFS completes, they’re unreachable, so we return -1.