How do you solve Rotting Oranges?

Initialize a queue with all rotten oranges and count fresh oranges. Perform BFS level-by-level, each level representing one minute. For each rotten orange, rot all adjacent fresh oranges, decrement fresh count, and add newly rotten oranges to the queue. Continue until no fresh oranges remain or no progress is possible. Return the elapsed time or -1 if fresh oranges remain.

What pattern does Rotting Oranges use?

The Pattern: BFS (Shortest Path on Unweighted Grid) The Heuristic: When a problem involves spreading or expanding effects step-by-step in a grid or graph with uniform cost, model it as a BFS where each layer represents one time unit or step, ensuring the first time a node is reached is the shortest path.

Rotting Oranges — BFS

Q: What is the time complexity of Rotting Oranges?

O(m * n). Each cell is enqueued and processed at most once. The BFS explores all reachable cells, resulting in O(m*n) operations.

Problem

Given a grid representing fresh and rotten oranges, return the minimum number of minutes until no fresh orange remains, or -1 if impossible.

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

Example

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

Output: 4

Initially, rotten oranges are at positions (0,0). In minute 1, oranges adjacent to (0,0) become rotten: (0,1) and (1,0). In minute 2, the rot spreads further to (0,2) and (1,1). In minute 3, (2,1) becomes rotten. In minute 4, (2,2) becomes rotten. After 4 minutes, no fresh oranges remain.

Approach

Straightforward Solution

A naive approach might repeatedly scan the grid to find fresh oranges adjacent to rotten ones and update them, repeating until no changes occur. This approach is inefficient and can be O(m^2 * n^2) in the worst case.

Core Observation

The rot spreads in discrete time steps to adjacent fresh oranges, which naturally models a shortest-path or level-by-level expansion problem on a grid graph.

Path to Optimal

Preview

Recognizing the problem as a shortest path in an unweighted grid, the optimal approach uses BFS starting from all initially rotten oranges simultaneously. Each BFS layer corresponds to one minute passing, and the BFS expansion simulates the rot spreading…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Initialize a queue with all rotten oranges and count fresh oranges. Perform BFS level-by-level, each level representing one minute…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(m * n)

Each cell is enqueued and processed at most once. The BFS explores all reachable cells, resulting in O(m*n) operations.

Space

O(m * n)

The queue can hold up to O(m*n) cells in the worst case, and the grid itself is O(m*n). No additional significant space is used.

Solution

Python

1import collections
2
3class Solution:
  def orangesRotting(self, grid: list[list[int]]) -> int:
      q = collections.deque()
      time, fresh = 0, 0
      ROWS, COLS = len(grid), len(grid[0])
8
      for r in range(ROWS):
          for c in range(COLS):
              if grid[r][c] == 1:
                  fresh += 1
              if grid[r][c] == 2:
                  q.append([r, c])
      
      directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
      while q and fresh > 0:
          for i in range(len(q)):
              r, c = q.popleft()
              for dr, dc in directions:
                  row, col = r + dr, c + dc
                  if (row < 0 or row == ROWS or
                      col < 0 or col == COLS or
                      grid[row][col] != 1):
                      continue
                  grid[row][col] = 2
                  q.append([row, col])
                  fresh -= 1
          time += 1
      
      return time if fresh == 0 else -1

Step-by-Step Solution

1

Initialize Queue with Rotten Oranges and Count Fresh Oranges

5q = collections.deque()
6time, fresh = 0, 0
7ROWS, COLS = len(grid), len(grid[0])
9for r in range(ROWS):
10    for c in range(COLS):
11        if grid[r][c] == 1:
12            fresh += 1
13        if grid[r][c] == 2:
14            q.append([r, c])

Objective

To prepare the BFS by identifying all starting points (rotten oranges) and the total number of fresh oranges to track progress.

Key Insight

Starting BFS from all rotten oranges simultaneously models the parallel spread of rot. Counting fresh oranges upfront allows the algorithm to detect when all have been rotted and to terminate early if impossible.

Interview Quick-Check

Core Logic

Enqueue all rotten oranges initially to simulate simultaneous rot spread from multiple sources.

State & Boundaries

Track the count of fresh oranges to know when the process is complete.

Common Pitfalls & Bugs

Forgetting to count fresh oranges or enqueue all rotten oranges leads to incorrect termination or incomplete BFS.

2

Simulate Rot Spread Using BFS Level-by-Level Expansion

To perform BFS, spreading rot to adjacent fresh oranges each minute until no fresh oranges remain or no further spread is possible.

3

Return Minimum Time or -1 if Fresh Oranges Remain

To output the total minutes elapsed if all fresh oranges have rotted, or -1 if some fresh oranges remain unreachable.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 5 Critical lines interviewers watch for.

Line 31 Critical

return time if fresh == 0 else -1

Return the total time if all fresh oranges have rotted, otherwise return -1.

Returning -1 when fresh oranges remain signals that some oranges cannot be rotted, while returning time otherwise gives the minimum minutes required, completing the problem's requirements.

Line 14 Critical

q.append([r, c])

Add the rotten orange's coordinates to the BFS queue.

This placement is critical to simulate parallel rot spread; starting BFS from all rotten oranges ensures the minimum time calculation is correct.

Line 19 Critical

r, c = q.popleft()

Dequeue the next rotten orange to process.

Dequeuing in FIFO order is fundamental to BFS correctness, guaranteeing that oranges are processed in order of increasing distance (time) from initial rotten sources.

Full line-by-line criticality + rationale for all 24 lines available on Pro.

Test Your Understanding

Why does BFS guarantee the minimum time to rot all fresh oranges?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Rotting Oranges from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Rotting Oranges drill

or drill a free problem

1	`import collections`
2
3	`class Solution:`
4	`def orangesRotting(self, grid: list[list[int]]) -> int:`
5	`q = collections.deque()`
6	`time, fresh = 0, 0`
7	`ROWS, COLS = len(grid), len(grid[0])`
8
9	`for r in range(ROWS):`
10	`for c in range(COLS):`
11	`if grid[r][c] == 1:`
12	`fresh += 1`
13	`if grid[r][c] == 2:`
14	`q.append([r, c])`
15
16	`directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]`
17	`while q and fresh > 0:`
18	`for i in range(len(q)):`
19	`r, c = q.popleft()`
20	`for dr, dc in directions:`
21	`row, col = r + dr, c + dc`
22	`if (row < 0 or row == ROWS or`
23	`col < 0 or col == COLS or`
24	`grid[row][col] != 1):`
25	`continue`
26	`grid[row][col] = 2`
27	`q.append([row, col])`
28	`fresh -= 1`
29	`time += 1`
30
31	`return time if fresh == 0 else -1`

5	`q = collections.deque()`
6	`time, fresh = 0, 0`
7	`ROWS, COLS = len(grid), len(grid[0])`
9	`for r in range(ROWS):`
10	`for c in range(COLS):`
11	`if grid[r][c] == 1:`
12	`fresh += 1`
13	`if grid[r][c] == 2:`
14	`q.append([r, c])`