994. Rotting Oranges

994

MediumGraph DFS and BFSBFS from all sources simultaneouslyMulti-source BFS (level-by-level)

Rotting Oranges

In an m x n grid each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange 4-directionally adjacent to a rotten one becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if some orange can never rot.

Open official problem prompt ↗

In plain English

Find the minimum minutes for rot to reach every fresh orange, or detect that some are unreachable.

Picture it like this

Like ink dropped simultaneously into a grid of blotting paper from several spots at once; you count how many seconds pass until the ink has soaked every reachable square.

Example

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Why: Rot spreads outward from (0,0); the farthest fresh orange at (2,2) becomes rotten after 4 minutes.

Constraints

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

Pattern lesson

See the pattern, then code

Multi-source BFS (level-by-level)

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Seed the queue with every rotten orange, then expand one full ring per minute; the number of rings processed until all fresh oranges rot is the answer.

New words, made simpleKnow these before the algorithm

Multi-source BFS: BFS seeded with many start cells so all frontiers advance together.
Level: One BFS wave, here corresponding to one minute of spreading.
Fresh count: A running tally of remaining fresh oranges used to detect unreachable cells.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Simulate minute by minute with full scans

Repeated full scans waste work compared to a frontier queue.

Each minute, scan the whole grid and rot neighbors of any rotten cell.

Time O((m*n)^2)Space O(m*n)

Best choiceMulti-source BFS by level

Each cell enters the queue once and levels give the exact minute.

Seed all rotten cells, expand one ring per minute, track fresh remaining.

Time O(m*n)Space O(m*n)

The rule we keep true

Invariant

After processing k levels, every orange within BFS distance k of an initial rotten orange is rotten, and none farther.

Why this is correct

Reasoning

BFS visits cells in nondecreasing distance from the sources, so the level at which a fresh orange rots equals its true shortest rot time; if any fresh orange is never reached, the fresh count stays positive.

The algorithm in three movesSay these aloud before coding

1Enqueue every rotten orange and count fresh ones

queue=[(0,0)], fresh=6

2Process the queue level by level, each level being one minute

min1: rot (0,1),(1,0); fresh=4

3Rot fresh neighbors, decrement the fresh count, enqueue them

min4: fresh=0 -> return 4

4After the loop, return the minutes if no fresh remain, else -1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readscan grid

2 · AskWhich cells start rotten?

3 · Update statequeue=[(0,0)], fresh=6, minutes=0

4 · ResultOne source enqueued

Key takeaway

Rot begins at the single source cell 2 and expands to its fresh neighbors each minute.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-14Seed sources and count fresh
Every rotten orange becomes a BFS start; fresh oranges are tallied for the termination check.
2
Lines 15-25Level-by-level spread
The fixed-size inner loop processes exactly one minute's frontier before incrementing minutes.
3
Lines 26Result
If any fresh orange remains unreachable the answer is -1, otherwise the elapsed minutes.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

No fresh oranges at all returns 0
Fresh orange isolated by empty cells returns -1
Grid with no rotten oranges but some fresh returns -1
All cells empty returns 0

Common beginner mistakes

Incrementing minutes even when no fresh oranges exist, giving 1 instead of 0
Not fixing the frontier size with len(queue) before the inner loop, mixing minutes together
Forgetting to mark a rotting orange as 2, causing it to be processed multiple times

Check your understanding

Why does the while loop include the 'fresh > 0' condition rather than just 'queue'?

PyPython 3 · solution.py

Optimal

1from collections import deque234class Solution:5    def orangesRotting(self, grid: list[list[int]]) -> int:6        rows, cols = len(grid), len(grid[0])7        queue = deque()8        fresh = 09        for r in range(rows):10            for c in range(cols):11                if grid[r][c] == 2:12                    queue.append((r, c))13                elif grid[r][c] == 1:14                    fresh += 115        minutes = 016        while queue and fresh > 0:17            for _ in range(len(queue)):18                r, c = queue.popleft()19                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):20                    nr, nc = r + dr, c + dc21                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:22                        grid[nr][nc] = 223                        fresh -= 124                        queue.append((nr, nc))25            minutes += 126        return minutes if fresh == 0 else -1

Time complexityO(m * n)Optimized

Space complexityO(m * n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMetaMicrosoftGoogle

Rotting Oranges

Rotting Oranges

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS