Rotting Oranges

Difficulty: Medium Source: NeetCode

Problem

You are given an m x n grid where each cell can have one of three values:

• 0 — empty cell
• 1 — fresh orange
• 2 — 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 it 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

Example 3: Input: grid = [[0,2]] Output: 0

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Multi-source BFS — spreading from multiple starting points simultaneously; same concept as Walls and Gates
• BFS for shortest distance — BFS levels naturally correspond to time steps

1. Brute Force (Simulate minute by minute)

Intuition

Simulate the process directly: in each minute, scan the entire grid and rot every fresh orange adjacent to a rotten one. Repeat until no fresh oranges remain or nothing changes. Count the rounds. This is O((M*N)²) in the worst case.

Algorithm

1. Count initial fresh oranges.
2. Repeat: scan the grid, collect newly rotten oranges, rot them, decrement fresh, increment minutes.
3. Stop when fresh == 0 (return minutes) or nothing changed (return -1).

Solution

def orangesRotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    fresh = sum(grid[r][c] == 1 for r in range(rows) for c in range(cols))
    minutes = 0

    while fresh > 0:
        to_rot = []
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                            to_rot.append((nr, nc))
        if not to_rot:
            return -1
        for r, c in to_rot:
            grid[r][c] = 2
            fresh -= 1
        minutes += 1

    return minutes


print(orangesRotting([[2,1,1],[1,1,0],[0,1,1]]))  # 4
print(orangesRotting([[2,1,1],[0,1,1],[1,0,1]]))  # -1
print(orangesRotting([[0,2]]))                     # 0

Complexity

• Time: O((M * N)²) — up to MN rounds, each scanning MN cells
• Space: O(M * N) for to_rot list

2. Multi-Source BFS

Intuition

All rotten oranges spread simultaneously, so this is exactly a multi-source BFS problem. Seed the queue with all initially rotten oranges, then run BFS. Each BFS level represents one minute of spreading. Track fresh oranges remaining — if any are left after BFS exhausts, return -1.

Algorithm

1. Count fresh oranges. Enqueue all initially rotten oranges.
2. Run BFS with minutes = 0. At each level:
   • Process all cells currently in the queue.
   • For each neighbor that is fresh: mark it rotten, decrement fresh, enqueue.
   • If we processed any cells in this round, increment minutes.
3. Return minutes if fresh == 0, else -1.

Solution

from collections import deque

def orangesRotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    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 += 1

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

    while queue and fresh > 0:
        minutes += 1
        for _ in range(len(queue)):
            r, c = queue.popleft()
            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] = 2
                    fresh -= 1
                    queue.append((nr, nc))

    return minutes if fresh == 0 else -1


print(orangesRotting([[2,1,1],[1,1,0],[0,1,1]]))  # 4
print(orangesRotting([[2,1,1],[0,1,1],[1,0,1]]))  # -1
print(orangesRotting([[0,2]]))                     # 0
print(orangesRotting([[1]]))                       # -1 (no rotten orange)
print(orangesRotting([[2]]))                       # 0 (no fresh oranges)

Complexity

• Time: O(M * N) — each cell is processed at most once
• Space: O(M * N) — queue size

Common Pitfalls

Counting minutes incorrectly. Only increment minutes when you actually rot oranges in that round. The condition while queue and fresh > 0 ensures the last iteration (when fresh hits 0) still counted correctly.

Returning -1 prematurely. Check fresh == 0 after BFS completes, not during. Fresh oranges isolated behind walls or empty cells will never be reached, and you can only detect this after BFS finishes.

Marking oranges before enqueueing. Set grid[nr][nc] = 2 before appending to the queue. If you mark after dequeuing, the same fresh orange can be enqueued multiple times from different rotten neighbors in the same minute.