LeetCode Problem 994

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Matrix

Solution

LeetCode 994, Rotting Oranges

Problem Statement

You are given a 2D grid where each cell represents one of three possible states:

• 0 means the cell is empty.
• 1 means the cell contains a fresh orange.
• 2 means the cell contains a rotten orange.

Every minute, any fresh orange that is directly adjacent to a rotten orange becomes rotten as well. Adjacency is only considered in the four cardinal directions: up, down, left, and right.

The goal is to determine the minimum number of minutes required until there are no fresh oranges left in the grid. If some fresh oranges can never become rotten because they are isolated, the function must return -1.

The input is an m x n matrix where both dimensions are at most 10. This is a relatively small grid, but the problem still requires careful simulation because the infection spreads simultaneously from multiple rotten oranges.

The important detail is that all currently rotten oranges spread at the same time during each minute. This means we are not processing one rotten orange completely before another. Instead, the spread happens level by level in time.

Several edge cases are important:

• A grid with no fresh oranges should immediately return 0.
• A grid with fresh oranges but no rotten oranges can never fully rot, so the answer is -1.
• Fresh oranges separated by empty cells may become unreachable.
• Multiple rotten oranges may infect different regions simultaneously.

Problem Understanding

This problem is fundamentally about simulating the spread of a condition across a grid over time.

Each rotten orange acts like a source of infection. Every minute, the infection spreads outward by one cell in the four valid directions. Since all rotten oranges spread simultaneously, this naturally forms layers of expansion.

The output is not the total number of oranges that rot, but the amount of time required until all reachable fresh oranges become rotten.

The constraints are small, but the structure of the problem strongly suggests a graph traversal interpretation. Every cell can be viewed as a node in a graph, and edges exist between adjacent cells. The infection spreads outward one level at a time, which is exactly the behavior modeled by Breadth-First Search, BFS.

Approaches

Brute Force Approach

A straightforward simulation approach would repeatedly scan the entire grid minute by minute.

During each pass:

1. Find all currently rotten oranges.
2. Mark adjacent fresh oranges to become rotten.
3. After finishing the scan, update the grid.
4. Repeat until no changes occur.

This works because it accurately simulates the minute-by-minute spread process. However, it repeatedly traverses the entire matrix even when only a few cells change.

If there are k minutes of spread and the grid contains m * n cells, the total complexity becomes approximately O(k * m * n). In the worst case, k can also approach m * n, leading to inefficient repeated work.

Optimal Approach

The key insight is that the rotting process behaves exactly like multi-source BFS.

Instead of repeatedly scanning the grid, we can:

• Start BFS from every rotten orange simultaneously.
• Process the infection layer by layer.
• Each BFS level represents one minute of elapsed time.

This is efficient because every orange is processed at most once.

BFS is ideal here because:

• Infection spreads uniformly outward.
• The first time we reach a fresh orange is the earliest minute it can rot.
• Simultaneous spreading maps naturally to queue-based level traversal.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((m × n)²)	O(1)	Repeatedly scans the entire grid every minute
Optimal BFS	O(m × n)	O(m × n)	Processes each cell at most once using multi-source BFS

Algorithm Walkthrough

1. Traverse the entire grid once to gather initial information.

During this traversal:

• Count the number of fresh oranges.
• Add every rotten orange position into a queue.

The queue represents all infection sources active at the current minute. 2. Handle the trivial case where there are no fresh oranges.

If the fresh orange count is already zero, return 0 immediately because no time is needed. 3. Start the BFS process.

Each iteration of the BFS loop represents one minute passing.

For the current queue size:

• Process only the oranges already rotten at the start of the minute.
• Newly infected oranges are added for processing in the next minute.

4. For each rotten orange, check its four neighboring cells.

The valid directions are:

• Up
• Down
• Left
• Right

For each neighbor:

• Ensure it is inside grid bounds.
• Check whether it contains a fresh orange.

5. When a fresh orange is found:

• Change it to rotten immediately.
• Decrease the fresh orange count.
• Add it to the queue.

This ensures it participates in spreading during the next minute. 6. After processing one BFS layer, increment the minute counter.

This accurately tracks how many rounds of spreading have occurred. 7. Continue until the queue becomes empty. 8. After BFS finishes:

• If fresh oranges still remain, return -1.
• Otherwise return the elapsed minute count.

Why it works

BFS guarantees that nodes are processed in increasing order of distance from the starting sources. Since each BFS layer corresponds to one minute of spread, the first time a fresh orange becomes rotten is the minimum possible time it could rot. Processing all initial rotten oranges simultaneously ensures the simulation exactly matches the problem rules.

Python Solution

from collections import deque
from typing import List

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

        queue = deque()
        fresh_count = 0

        # Collect all rotten oranges and count fresh oranges
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 2:
                    queue.append((row, col))
                elif grid[row][col] == 1:
                    fresh_count += 1

        # No fresh oranges already
        if fresh_count == 0:
            return 0

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

        # Multi-source BFS
        while queue and fresh_count > 0:
            current_level_size = len(queue)

            for _ in range(current_level_size):
                row, col = queue.popleft()

                for dr, dc in directions:
                    new_row = row + dr
                    new_col = col + dc

                    # Check bounds and fresh orange
                    if (
                        0 <= new_row < rows
                        and 0 <= new_col < cols
                        and grid[new_row][new_col] == 1
                    ):
                        # Rot the orange
                        grid[new_row][new_col] = 2
                        fresh_count -= 1

                        queue.append((new_row, new_col))

            minutes += 1

        return minutes if fresh_count == 0 else -1

The implementation begins by scanning the grid once to locate all rotten oranges and count all fresh oranges. Rotten oranges are inserted into a queue because BFS requires processing nodes in first-in, first-out order.

The fresh_count variable is important because it allows the algorithm to quickly determine whether all oranges have been infected.

The BFS loop processes the queue level by level. The variable current_level_size ensures that only oranges rotten at the start of the current minute are processed. Any newly rotten oranges are deferred to the next BFS layer, which correctly models simultaneous spreading.

The four direction offsets simplify neighbor traversal while avoiding duplicated code.

Finally, after BFS completes, the algorithm checks whether any fresh oranges remain unreachable. If so, the function returns -1.

Go Solution

package main

func orangesRotting(grid [][]int) int {
	rows := len(grid)
	cols := len(grid[0])

	type Pair struct {
		row int
		col int
	}

	queue := []Pair{}
	freshCount := 0

	// Collect rotten oranges and count fresh oranges
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if grid[r][c] == 2 {
				queue = append(queue, Pair{r, c})
			} else if grid[r][c] == 1 {
				freshCount++
			}
		}
	}

	// No fresh oranges
	if freshCount == 0 {
		return 0
	}

	minutes := 0

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	// Multi-source BFS
	for len(queue) > 0 && freshCount > 0 {
		levelSize := len(queue)

		for i := 0; i < levelSize; i++ {
			current := queue[0]
			queue = queue[1:]

			for _, dir := range directions {
				newRow := current.row + dir[0]
				newCol := current.col + dir[1]

				if newRow >= 0 &&
					newRow < rows &&
					newCol >= 0 &&
					newCol < cols &&
					grid[newRow][newCol] == 1 {

					grid[newRow][newCol] = 2
					freshCount--

					queue = append(queue, Pair{newRow, newCol})
				}
			}
		}

		minutes++
	}

	if freshCount == 0 {
		return minutes
	}

	return -1
}

The Go implementation follows the same algorithmic structure as the Python version. Since Go does not provide a built-in deque structure, a slice is used as the BFS queue. Elements are removed from the front using slicing.

Go also requires an explicit struct definition for storing row and column coordinates. Integer overflow is not a concern here because the grid dimensions are very small.

Worked Examples

Example 1

Input:

[[2,1,1],
 [1,1,0],
 [0,1,1]]

Initial state:

Minute	Queue	Fresh Count
0	[(0,0)]	6

Grid:

2 1 1
1 1 0
0 1 1

After minute 1:

Newly rotten:

• (0,1)
• (1,0)

Minute	Queue	Fresh Count
1	[(0,1), (1,0)]	4

Grid:

2 2 1
2 1 0
0 1 1

After minute 2:

Newly rotten:

• (0,2)
• (1,1)

Minute	Queue	Fresh Count
2	[(0,2), (1,1)]	2

Grid:

2 2 2
2 2 0
0 1 1

After minute 3:

Newly rotten:

• (2,1)

Minute	Queue	Fresh Count
3	[(2,1)]	1

Grid:

2 2 2
2 2 0
0 2 1

After minute 4:

Newly rotten:

• (2,2)

Minute	Queue	Fresh Count
4	[(2,2)]	0

All oranges are rotten, return 4.

Example 2

Input:

[[2,1,1],
 [0,1,1],
 [1,0,1]]

The orange at (2,0) is isolated because empty cells block all possible paths.

Eventually BFS stops while fresh oranges still remain.

Result:

-1

Example 3

Input:

[[0,2]]

There are no fresh oranges initially.

The algorithm immediately returns:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m × n)	Every cell is visited at most once
Space	O(m × n)	The BFS queue can contain many grid cells

The algorithm is efficient because each orange transitions from fresh to rotten only once. No repeated rescanning of the grid is needed. The queue stores only active BFS frontier cells, and in the worst case this may include most cells in the grid.

Test Cases

from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        from collections import deque

        rows = len(grid)
        cols = len(grid[0])

        queue = deque()
        fresh_count = 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_count += 1

        if fresh_count == 0:
            return 0

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

        while queue and fresh_count > 0:
            for _ in range(len(queue)):
                r, c = queue.popleft()

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

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

            minutes += 1

        return minutes if fresh_count == 0 else -1

solution = Solution()

# Example 1
assert solution.orangesRotting([[2,1,1],[1,1,0],[0,1,1]]) == 4  # normal spreading

# Example 2
assert solution.orangesRotting([[2,1,1],[0,1,1],[1,0,1]]) == -1  # unreachable fresh orange

# Example 3
assert solution.orangesRotting([[0,2]]) == 0  # no fresh oranges initially

# Single fresh orange with no rotten source
assert solution.orangesRotting([[1]]) == -1  # impossible to rot

# Single rotten orange
assert solution.orangesRotting([[2]]) == 0  # already rotten

# All empty cells
assert solution.orangesRotting([[0,0],[0,0]]) == 0  # nothing to process

# One-step infection
assert solution.orangesRotting([[2,1]]) == 1  # immediate neighbor

# Multiple infection sources
assert solution.orangesRotting([[2,1,1],[1,1,1],[1,1,2]]) == 2  # simultaneous BFS

# Fresh oranges separated by empty cells
assert solution.orangesRotting([[2,0,1]]) == -1  # blocked path

# Large connected region
assert solution.orangesRotting([
    [2,1,1,1],
    [1,1,1,1],
    [1,1,1,1]
]) == 5  # maximum spread depth

Test Summary

Test	Why
[[2,1,1],[1,1,0],[0,1,1]]	Standard multi-minute spread
[[2,1,1],[0,1,1],[1,0,1]]	Detects unreachable fresh oranges
[[0,2]]	No fresh oranges initially
[[1]]	No rotten source exists
[[2]]	Already completely rotten
[[0,0],[0,0]]	Entirely empty grid
[[2,1]]	Single-step spread
[[2,1,1],[1,1,1],[1,1,2]]	Multiple simultaneous BFS sources
[[2,0,1]]	Empty cell blocks infection
Large connected region	Tests maximum propagation depth

Edge Cases

No Fresh Oranges Initially

A common bug is unnecessarily running BFS even when there are no fresh oranges. In a grid like [[0,2]], the correct answer is 0 because nothing needs to happen. The implementation handles this by counting fresh oranges during initialization and immediately returning 0 if the count is zero.

Fresh Oranges With No Rotten Source

If the grid contains fresh oranges but no rotten oranges, infection can never begin. For example:

[[1,1],
 [1,1]]

A naive implementation might incorrectly return 0 because the queue starts empty. The solution avoids this by checking whether fresh oranges remain after BFS completes. If they do, it returns -1.

Isolated Fresh Oranges

Fresh oranges can become trapped behind empty cells. For example:

[[2,0,1]]

The fresh orange is unreachable because infection cannot pass through empty cells. BFS naturally handles this because unreachable cells are never visited. After traversal finishes, fresh_count remains positive, causing the algorithm to correctly return -1.

Multiple Rotten Sources

Another subtle issue is ensuring simultaneous spread from multiple rotten oranges. Processing them sequentially instead of level by level can produce incorrect timing results. The BFS level-order traversal guarantees that all oranges infected during minute t only begin infecting others during minute t + 1.