Rotting Oranges

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.

Q: 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.

Medium BFS

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

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. This approach guarantees the minimum time to rot all reachable fresh oranges.

Optimal Approach

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.

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.

Pattern Spotlight

BFS (Shortest Path on Unweighted Grid)

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.

Solution

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

1import java.util.*;
2
3class Solution {
  public int orangesRotting(int[][] grid) {
      Queue<int[]> q = new LinkedList<>();
      int time = 0, fresh = 0;
      int ROWS = grid.length, COLS = grid[0].length;
8
      for (int r = 0; r < ROWS; r++) {
          for (int c = 0; c < COLS; c++) {
              if (grid[r][c] == 1) {
                  fresh++;
              }
              if (grid[r][c] == 2) {
                  q.offer(new int[]{r, c});
              }
          }
      }
19
      int[][] directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};
      while (!q.isEmpty() && fresh > 0) {
          int size = q.size();
          for (int i = 0; i < size; i++) {
              int[] point = q.poll();
              int r = point[0], c = point[1];
              for (int[] d : directions) {
                  int row = r + d[0], col = c + d[1];
                  if (row < 0 || row == ROWS || col < 0 || col == COLS || grid[row][col] != 1) {
                      continue;
                  }
                  grid[row][col] = 2;
                  q.offer(new int[]{row, col});
                  fresh--;
              }
          }
          time++;
      }
38
      return fresh == 0 ? time : -1;
  }
41}

1#include <vector>
2#include <queue>
3
4using namespace std;
5
6class Solution {
7public:
  int orangesRotting(vector<vector<int>>& grid) {
      queue<pair<int,int>> q;
      int time = 0, fresh = 0;
      int ROWS = grid.size(), COLS = grid[0].size();
12
      for (int r = 0; r < ROWS; r++) {
          for (int c = 0; c < COLS; c++) {
              if (grid[r][c] == 1) {
                  fresh++;
              }
              if (grid[r][c] == 2) {
                  q.push({r, c});
              }
          }
      }
23
      vector<pair<int,int>> directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};
      while (!q.empty() && fresh > 0) {
          int size = q.size();
          for (int i = 0; i < size; i++) {
              auto [r, c] = q.front();
              q.pop();
              for (auto& d : directions) {
                  int row = r + d.first, col = c + d.second;
                  if (row < 0 || row == ROWS || col < 0 || col == COLS || grid[row][col] != 1) {
                      continue;
                  }
                  grid[row][col] = 2;
                  q.push({row, col});
                  fresh--;
              }
          }
          time++;
      }
42
      return fresh == 0 ? time : -1;
  }
45};

1var orangesRotting = function(grid) {
  const q = [];
  let time = 0, fresh = 0;
  const ROWS = grid.length, COLS = grid[0].length;
5
  for (let r = 0; r < ROWS; r++) {
      for (let c = 0; c < COLS; c++) {
          if (grid[r][c] === 1) {
              fresh++;
          }
          if (grid[r][c] === 2) {
              q.push([r, c]);
          }
      }
  }
16
  const directions = [[0,1], [0,-1], [1,0], [-1,0]];
  let head = 0;
  while (head < q.length && fresh > 0) {
      let size = q.length - head;
      for (let i = 0; i < size; i++) {
          const [r, c] = q[head++];
          for (const [dr, dc] of directions) {
              const row = r + dr, col = c + dc;
              if (row < 0 || row === ROWS || col < 0 || col === COLS || grid[row][col] !== 1) {
                  continue;
              }
              grid[row][col] = 2;
              q.push([row, col]);
              fresh--;
          }
      }
      time++;
  }
35
  return fresh === 0 ? time : -1;
37};

Step-by-Step Solution

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.

Simulate Rot Spread Using BFS Level-by-Level Expansion

16directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
17while 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

Objective

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

Key Insight

Each BFS iteration corresponds to one minute passing. Processing all nodes in the current queue layer before incrementing time ensures the time count accurately reflects the number of minutes elapsed. Rotting adjacent fresh oranges and adding them to the queue models the spread of rot in discrete time steps.

Interview Quick-Check

Core Logic

Process all rotten oranges in the current minute before incrementing time to correctly simulate simultaneous rot spread.

State & Boundaries

Stop BFS when no fresh oranges remain or when no new oranges can be rotted.

Common Pitfalls & Bugs

Incrementing time inside the inner loop or before processing all current rotten oranges leads to incorrect timing.

Complexity

Each cell is processed once, ensuring O(m*n) time complexity.

Return Minimum Time or -1 if Fresh Oranges Remain

31	`return time if fresh == 0 else -1`

Objective

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

Key Insight

If fresh oranges remain after BFS completes, it means they are isolated and cannot be rotted. Returning -1 signals this impossibility. Otherwise, the time variable accurately reflects the minimum minutes needed.

Interview Quick-Check

Core Logic

Return time only if all fresh oranges have rotted; otherwise, return -1.

State & Boundaries

Check fresh count after BFS to determine if the process was successful.

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.

Line 26 Critical

grid[row][col] = 2

Mark the adjacent fresh orange as rotten.

Marking the orange as rotten immediately upon discovery prevents multiple enqueues of the same cell and ensures BFS correctness.

Line 29 Critical

time += 1

Increment the time counter after processing one BFS layer.

Incrementing time after processing all current rotten oranges ensures the time count accurately reflects the number of minutes elapsed.

Line 5 Core

q = collections.deque()

Initialize a queue to hold coordinates of rotten oranges.

The queue is essential for BFS traversal, enabling level-by-level processing of rotten oranges to simulate rot spread.

Line 13 Core

if grid[r][c] == 2:

Check if the current cell contains a rotten orange.

Rotten oranges are the starting points for BFS and must be enqueued initially.

Line 17 Core

while q and fresh > 0:

Continue BFS while there are rotten oranges to process and fresh oranges remain.

The loop condition ensures BFS runs only as long as progress is possible and needed.

Line 18 Core

for i in range(len(q)):

Iterate over all rotten oranges in the current BFS layer.

Processing all nodes at the current level simulates one minute passing in the rot spread.

Line 24 Core

grid[row][col] != 1):

Check if the adjacent cell is not a fresh orange.

Only fresh oranges can be rotted; others are skipped to avoid redundant processing.

Line 27 Core

q.append([row, col])

Add the newly rotten orange to the BFS queue.

Enqueuing newly rotten oranges schedules them for processing in the next minute.

Line 28 Core

fresh -= 1

Decrement the count of fresh oranges remaining.

Tracking fresh oranges allows early termination when all have rotted.

Line 6 Core

time, fresh = 0, 0

Initialize time counter and fresh orange count.

Tracking time measures the minutes elapsed, and counting fresh oranges allows detection of completion or impossibility.

Line 11 Core

if grid[r][c] == 1:

Check if the current cell contains a fresh orange.

Identifying fresh oranges is necessary to track how many remain to be rotted.

Line 12 Core

fresh += 1

Increment the count of fresh oranges.

Accurate fresh orange count is critical for determining when the BFS can terminate successfully.

Line 22 Core

if (row < 0 or row == ROWS or

Check if the adjacent row is out of grid bounds.

Boundary checks prevent invalid memory access and incorrect processing.

Line 23 Core

col < 0 or col == COLS or

Check if the adjacent column is out of grid bounds.

Ensures neighbor coordinates are valid within the grid.

Line 25 Core

continue

Skip processing if any boundary or state condition fails.

This continue statement prevents invalid or unnecessary BFS expansions.

Line 16 Standard

directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

Define the four possible directions for adjacent cells.

These directions enable exploration of neighbors in the grid, essential for BFS expansion.

Line 20 Standard

for dr, dc in directions:

Iterate over all four adjacent directions.

Exploring neighbors is necessary to spread the rot to fresh oranges.

Line 9 Standard

for r in range(ROWS):

Iterate over each row in the grid.

This loop scans the entire grid to identify initial rotten and fresh oranges.

Line 10 Standard

for c in range(COLS):

Iterate over each column in the current row.

Nested loop ensures every cell is visited for accurate counting and initialization.

Line 21 Standard

row, col = r + dr, c + dc

Calculate the coordinates of the adjacent cell.

Computing neighbor positions enables boundary and state checks before processing.

Line 7 Basic

ROWS, COLS = len(grid), len(grid[0])

Store the number of rows and columns in the grid.

Caching grid dimensions simplifies boundary checks and improves code readability.

Test Your Understanding

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

Because BFS explores the grid in layers, each layer representing one minute, the first time a fresh orange is reached and rotted corresponds to the shortest time it takes for the rot to spread there.

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`

1	`import java.util.*;`
2
3	`class Solution {`
4	`public int orangesRotting(int[][] grid) {`
5	`Queue<int[]> q = new LinkedList<>();`
6	`int time = 0, fresh = 0;`
7	`int ROWS = grid.length, COLS = grid[0].length;`
8
9	`for (int r = 0; r < ROWS; r++) {`
10	`for (int c = 0; c < COLS; c++) {`
11	`if (grid[r][c] == 1) {`
12	`fresh++;`
13	`}`
14	`if (grid[r][c] == 2) {`
15	`q.offer(new int[]{r, c});`
16	`}`
17	`}`
18	`}`
19
20	`int[][] directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};`
21	`while (!q.isEmpty() && fresh > 0) {`
22	`int size = q.size();`
23	`for (int i = 0; i < size; i++) {`
24	`int[] point = q.poll();`
25	`int r = point[0], c = point[1];`
26	`for (int[] d : directions) {`
27	`int row = r + d[0], col = c + d[1];`
28	`if (row < 0 \|\| row == ROWS \|\| col < 0 \|\| col == COLS \|\| grid[row][col] != 1) {`
29	`continue;`
30	`}`
31	`grid[row][col] = 2;`
32	`q.offer(new int[]{row, col});`
33	`fresh--;`
34	`}`
35	`}`
36	`time++;`
37	`}`
38
39	`return fresh == 0 ? time : -1;`
40	`}`
41	`}`

1	`#include <vector>`
2	`#include <queue>`
3
4	`using namespace std;`
5
6	`class Solution {`
7	`public:`
8	`int orangesRotting(vector<vector<int>>& grid) {`
9	`queue<pair<int,int>> q;`
10	`int time = 0, fresh = 0;`
11	`int ROWS = grid.size(), COLS = grid[0].size();`
12
13	`for (int r = 0; r < ROWS; r++) {`
14	`for (int c = 0; c < COLS; c++) {`
15	`if (grid[r][c] == 1) {`
16	`fresh++;`
17	`}`
18	`if (grid[r][c] == 2) {`
19	`q.push({r, c});`
20	`}`
21	`}`
22	`}`
23
24	`vector<pair<int,int>> directions = {{0,1}, {0,-1}, {1,0}, {-1,0}};`
25	`while (!q.empty() && fresh > 0) {`
26	`int size = q.size();`
27	`for (int i = 0; i < size; i++) {`
28	`auto [r, c] = q.front();`
29	`q.pop();`
30	`for (auto& d : directions) {`
31	`int row = r + d.first, col = c + d.second;`
32	`if (row < 0 \|\| row == ROWS \|\| col < 0 \|\| col == COLS \|\| grid[row][col] != 1) {`
33	`continue;`
34	`}`
35	`grid[row][col] = 2;`
36	`q.push({row, col});`
37	`fresh--;`
38	`}`
39	`}`
40	`time++;`
41	`}`
42
43	`return fresh == 0 ? time : -1;`
44	`}`
45	`};`

1	`var orangesRotting = function(grid) {`
2	`const q = [];`
3	`let time = 0, fresh = 0;`
4	`const ROWS = grid.length, COLS = grid[0].length;`
5
6	`for (let r = 0; r < ROWS; r++) {`
7	`for (let c = 0; c < COLS; c++) {`
8	`if (grid[r][c] === 1) {`
9	`fresh++;`
10	`}`
11	`if (grid[r][c] === 2) {`
12	`q.push([r, c]);`
13	`}`
14	`}`
15	`}`
16
17	`const directions = [[0,1], [0,-1], [1,0], [-1,0]];`
18	`let head = 0;`
19	`while (head < q.length && fresh > 0) {`
20	`let size = q.length - head;`
21	`for (let i = 0; i < size; i++) {`
22	`const [r, c] = q[head++];`
23	`for (const [dr, dc] of directions) {`
24	`const row = r + dr, col = c + dc;`
25	`if (row < 0 \|\| row === ROWS \|\| col < 0 \|\| col === COLS \|\| grid[row][col] !== 1) {`
26	`continue;`
27	`}`
28	`grid[row][col] = 2;`
29	`q.push([row, col]);`
30	`fresh--;`
31	`}`
32	`}`
33	`time++;`
34	`}`
35
36	`return fresh === 0 ? time : -1;`
37	`};`

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])`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize Queue with Rotten Oranges and Count Fresh Oranges

Simulate Rot Spread Using BFS Level-by-Level Expansion

Return Minimum Time or -1 if Fresh Oranges Remain

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.