LeetCode 994: Rotting Oranges

Problem Restatement

We are given an m x n grid.

Each cell can have one of three values:

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

The four directions are:

up, down, left, right

Diagonal cells do not count.

We need to return the minimum number of minutes needed until no fresh orange remains.

If some fresh orange can never become rotten, return -1.

The official constraints are 1 <= m, n <= 10, and each cell is 0, 1, or 2. (leetcode.com)

Input and Output

Function shape:

def orangesRotting(grid: list[list[int]]) -> int:
    ...

Examples

Example 1:

grid = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1],
]

Minute 0:

2 1 1
1 1 0
0 1 1

After minute 1:

2 2 1
2 1 0
0 1 1

After minute 2:

2 2 2
2 2 0
0 1 1

After minute 3:

2 2 2
2 2 0
0 2 1

After minute 4:

2 2 2
2 2 0
0 2 2

Answer:

4

Example 2:

grid = [
    [2, 1, 1],
    [0, 1, 1],
    [1, 0, 1],
]

The fresh orange in the bottom-left corner cannot be reached from any rotten orange because rotting only spreads through 4-directional adjacency.

Answer:

-1

Example 3:

grid = [[0, 2]]

There are no fresh oranges at the start.

Answer:

0

First Thought: Simulate Minute by Minute

A direct way is to repeatedly scan the whole grid.

During each minute:

1. Find all rotten oranges.
2. Mark all adjacent fresh oranges to become rotten.
3. Apply those changes.
4. Repeat until no fresh oranges remain or no new oranges rot.

This works, but it scans the grid again and again.

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        minutes = 0

        while True:
            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 = r + dr
                            nc = c + dc

                            if 0 <= nr < rows and 0 <= nc < cols:
                                if grid[nr][nc] == 1:
                                    to_rot.append((nr, nc))

            if not to_rot:
                break

            for r, c in to_rot:
                grid[r][c] = 2

            minutes += 1

        for row in grid:
            if 1 in row:
                return -1

        return minutes

This follows the process, but it does more work than needed.

Problem With Repeated Scanning

Every minute, the brute force simulation scans the full grid.

But only newly rotten oranges can spread rot in the next minute.

Old rotten oranges do not need to be processed repeatedly.

This is a shortest-distance spread problem on a grid, so BFS is the natural fit.

Key Insight

All initially rotten oranges begin spreading at the same time.

That makes this a multi-source BFS problem.

We start the BFS queue with every rotten orange already in the grid.

Each BFS layer represents one minute.

When we process all oranges currently in the queue, they rot their fresh neighbors. Those newly rotten oranges become the next layer.

So:

Algorithm

First scan the grid.

During this scan:

1. Add all rotten oranges to a queue.
2. Count all fresh oranges.

If there are no fresh oranges, return 0.

Then run BFS:

1. Process one full queue layer at a time.
2. For each rotten orange in the current layer, check four neighbors.
3. If a neighbor is fresh:
   • mark it rotten
   • decrease the fresh count
   • add it to the queue
4. After processing the layer, increment the minute count only if at least one fresh orange rotted.

At the end:

• If fresh == 0, return minutes.
• Otherwise, return -1.

Correctness

The queue initially contains every rotten orange present at minute 0.

BFS processes the grid layer by layer. Every cell added during one layer is exactly one minute farther from some initially rotten orange than the cells in the previous layer.

When a fresh orange is first reached by BFS, it is reached in the minimum possible number of minutes, because BFS explores all positions reachable in t minutes before any position reachable in t + 1 minutes.

The algorithm marks a fresh orange rotten when it is first reached, then never processes it as fresh again. Therefore, every orange is rotted at its earliest possible minute.

If all fresh oranges are reached, the last BFS layer that rotted an orange gives the minimum time needed for the whole grid.

If some fresh orange remains after BFS ends, then it was not reachable from any initially rotten orange through non-empty adjacent cells. Therefore, it can never rot, so returning -1 is correct.

Complexity

Let m = len(grid) and n = len(grid[0]).

Implementation

from collections import deque

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = 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

        if fresh == 0:
            return 0

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

        while queue and fresh > 0:
            level_size = len(queue)
            rotted_this_minute = False

            for _ in range(level_size):
                r, c = queue.popleft()

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

                    if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
                        continue

                    if grid[nr][nc] != 1:
                        continue

                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
                    rotted_this_minute = True

            if rotted_this_minute:
                minutes += 1

        if fresh == 0:
            return minutes

        return -1

Code Explanation

We collect all initial rotten oranges:

queue = deque()
fresh = 0

During the first scan, rotten oranges become BFS sources:

if grid[r][c] == 2:
    queue.append((r, c))

Fresh oranges are counted:

elif grid[r][c] == 1:
    fresh += 1

If there are no fresh oranges, no time is needed:

if fresh == 0:
    return 0

The BFS runs while there are rotten oranges that can spread and fresh oranges still remain:

while queue and fresh > 0:

Each loop processes one minute:

level_size = len(queue)

For each rotten orange, check its four neighbors:

for dr, dc in directions:

Ignore positions outside the grid:

if nr < 0 or nr >= rows or nc < 0 or nc >= cols:
    continue

Ignore cells that are not fresh:

if grid[nr][nc] != 1:
    continue

When a fresh orange rots, update the grid and queue:

grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))

After BFS, if no fresh oranges remain, return the minutes:

if fresh == 0:
    return minutes

Otherwise, some fresh orange was unreachable:

return -1

Testing

def run_tests():
    s = Solution()

    assert s.orangesRotting([
        [2, 1, 1],
        [1, 1, 0],
        [0, 1, 1],
    ]) == 4

    assert s.orangesRotting([
        [2, 1, 1],
        [0, 1, 1],
        [1, 0, 1],
    ]) == -1

    assert s.orangesRotting([[0, 2]]) == 0

    assert s.orangesRotting([[1]]) == -1

    assert s.orangesRotting([[2, 1]]) == 1

    print("all tests passed")

run_tests()