Log inSign up
mediumLeetCodeNot Started

Rotting Oranges

You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

You are given an m x n grid where each cell can have one of three values: - 0 representing an empty cell, - 1 representing a fresh orange, or - 2 representing a rotten orange.

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

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

---

### Examples

Example 1: ``text Input: grid = [ [2,1,1], [1,1,0], [0,1,1] ] Output: 4 Explanation: Minute 0: Rotten orange at (0, 0). 6 fresh oranges. Minute 1: Rot spreads to (0, 1) and (1, 0). 4 fresh left. Minute 2: Rot spreads to (0, 2) and (1, 1). 2 fresh left. Minute 3: Rot spreads to (2, 1). 1 fresh left. Minute 4: Rot spreads to (2, 2). 0 fresh left. Total time = 4 minutes.

Example 2: ``text Input: grid = [ [2,1,1], [0,1,1], [1,0,1] ] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3: ``text Input: grid = [[0,2]] Output: 0 Explanation: Since there are already 0 fresh oranges at minute 0, the answer is just 0.

---

### Constraints - m == grid.length - n == grid[i].length - 1 <= m, n <= 10 - grid[i][j] is 0, 1, or 2.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Implement multi-source BFS with multiple initial queue entries.
  • Handle simultaneous time-step tracking using level-size chunking.
  • Correctly manage edge cases like zero fresh oranges at time 0.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Simultaneous spreading from multiple source points
  • Shortest time for infection/spread across a 2D grid
  • 4-directional adjacency with cell state transitions

Algorithmic Decision Tree:

  • Multi-source spread at uniform unit time -> Use Multi-Source BFS.
  • Initialize queue with all sources at t = 0.
  • Process queue level-by-level using levelSize = q.size().

Connected Patterns:

01 MatrixShortest Path in Binary MatrixWalls and Gates

1. Round-by-Round Grid Simulation

Intuition

In each round, scan the entire grid. For every rotten orange, identify fresh neighbors and mark them as newly rotten in a next-state grid. Repeat until a round produces no new rotten oranges.

Algorithm

  1. Initialize minutes = 0.
  2. Loop indefinitely:
  3. Create nextGrid = copy of grid, changed = false.
  4. Scan all (r, c):
  5. If grid[r][c] == 2:
  6. Check 4 neighbors (nr, nc):
  7. If grid[nr][nc] == 1:
  8. nextGrid[nr][nc] = 2, changed = true.
  9. If !changed: break.
  10. grid = nextGrid, minutes++.
  11. Check if any cell in grid has value 1: if so return -1, else return minutes.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 int orangesRotting(std::vector<std::vector<int>>& grid) {
7 int m = grid.size();
8 int n = grid[0].size();
9 int minutes = 0;
10 int dr[] = {-1, 1, 0, 0};
11 int dc[] = {0, 0, -1, 1};
12
13 while (true) {
14 std::vector<std::vector<int>> nextGrid = grid;
15 bool changed = false;
16
17 for (int r = 0; r < m; ++r) {
18 for (int c = 0; c < n; ++c) {
19 if (grid[r][c] == 2) {
20 for (int k = 0; k < 4; ++k) {
21 int nr = r + dr[k];
22 int nc = c + dc[k];
23 if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
24 nextGrid[nr][nc] = 2;
25 changed = true;
26 }
27 }
28 }
29 }
30 }
31
32 if (!changed) break;
33 grid = std::move(nextGrid);
34 minutes++;
35 }
36
37 for (int r = 0; r < m; ++r) {
38 for (int c = 0; c < n; ++c) {
39 if (grid[r][c] == 1) return -1;
40 }
41 }
42 return minutes;
43 }
44};
45
46int main() {
47 Solution sol;
48 std::vector<std::vector<int>> grid = {
49 {2, 1, 1},
50 {1, 1, 0},
51 {0, 1, 1}
52 };
53 std::cout << "Simulation Minutes: " << sol.orangesRotting(grid) << " (Expected: 4)\n";
54 return 0;
55}

Time & Space Complexity

  • Time complexity: O((m * n)^2)
  • Space complexity: O(m * n)

2. Multi-Source BFS with Time Matrix

Intuition

Treat rotten oranges as multi-source seeds with time 0. Spread rot like Dijkstra/BFS distance relaxation: neighbor time = curr time + 1. The maximum time among fresh oranges gives the answer.

Algorithm

  1. Initialize dist[m][n] to infinity (-1).
  2. Initialize queue q. Push all (r, c) with grid[r][c] == 2, setting dist[r][c] = 0.
  3. While queue is not empty:
  4. Pop (r, c).
  5. For 4 neighbors (nr, nc):
  6. If in bounds, grid[nr][nc] == 1, and dist[nr][nc] == -1:
  7. dist[nr][nc] = dist[r][c] + 1.
  8. Push (nr, nc) to queue.
  9. Scan grid: if any cell has grid[r][c] == 1 and dist[r][c] == -1, return -1.
  10. Return maximum value in dist.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <algorithm>
5
6class Solution {
7public:
8 int orangesRotting(std::vector<std::vector<int>>& grid) {
9 int m = grid.size();
10 int n = grid[0].size();
11 std::vector<std::vector<int>> dist(m, std::vector<int>(n, -1));
12 std::queue<std::pair<int, int>> q;
13
14 for (int r = 0; r < m; ++r) {
15 for (int c = 0; c < n; ++c) {
16 if (grid[r][c] == 2) {
17 dist[r][c] = 0;
18 q.push({r, c});
19 }
20 }
21 }
22
23 int dr[] = {-1, 1, 0, 0};
24 int dc[] = {0, 0, -1, 1};
25
26 while (!q.empty()) {
27 auto [r, c] = q.front();
28 q.pop();
29
30 for (int i = 0; i < 4; ++i) {
31 int nr = r + dr[i];
32 int nc = c + dc[i];
33 if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1 && dist[nr][nc] == -1) {
34 dist[nr][nc] = dist[r][c] + 1;
35 q.push({nr, nc});
36 }
37 }
38 }
39
40 int maxTime = 0;
41 for (int r = 0; r < m; ++r) {
42 for (int c = 0; c < n; ++c) {
43 if (grid[r][c] == 1) {
44 if (dist[r][c] == -1) return -1;
45 maxTime = std::max(maxTime, dist[r][c]);
46 }
47 }
48 }
49 return maxTime;
50 }
51};
52
53int main() {
54 Solution sol;
55 std::vector<std::vector<int>> grid = {
56 {2, 1, 1},
57 {1, 1, 0},
58 {0, 1, 1}
59 };
60 std::cout << "Distance BFS Minutes: " << sol.orangesRotting(grid) << " (Expected: 4)\n";
61 return 0;
62}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. Canonical Multi-Source BFS with Level Chunking (Optimal)

Intuition

Processing the queue in batches of size = q.size() corresponds directly to 1 minute of real-world time. Mutating fresh oranges from 1 to 2 acts as the visited indicator in place. If fresh reaches 0, return elapsed minutes.

Algorithm

  1. Initialize queue q and freshCount = 0.
  2. Scan grid: push all (r, c) with value 2 into q; count cells with value 1 into freshCount.
  3. If freshCount == 0, return 0.
  4. Initialize minutes = 0.
  5. Define directions: [(-1, 0), (1, 0), (0, -1), (0, 1)].
  6. While queue is not empty and freshCount > 0:
  7. levelSize = q.size().
  8. For i = 0 to levelSize - 1:
  9. Pop (r, c).
  10. For each direction (dr, dc):
  11. nr = r + dr, nc = c + dc.
  12. If in bounds and grid[nr][nc] == 1:
  13. grid[nr][nc] = 2 (rot it).
  14. freshCount--.
  15. Push (nr, nc) to queue.
  16. minutes++.
  17. Return freshCount == 0 ? minutes : -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 int orangesRotting(std::vector<std::vector<int>>& grid) {
8 int m = grid.size();
9 int n = grid[0].size();
10 std::queue<std::pair<int, int>> q;
11 int freshCount = 0;
12
13 for (int r = 0; r < m; ++r) {
14 for (int c = 0; c < n; ++c) {
15 if (grid[r][c] == 2) {
16 q.push({r, c});
17 } else if (grid[r][c] == 1) {
18 freshCount++;
19 }
20 }
21 }
22
23 if (freshCount == 0) return 0;
24
25 int minutes = 0;
26 int dr[] = {-1, 1, 0, 0};
27 int dc[] = {0, 0, -1, 1};
28
29 while (!q.empty() && freshCount > 0) {
30 int levelSize = q.size();
31 for (int i = 0; i < levelSize; ++i) {
32 auto [r, c] = q.front();
33 q.pop();
34
35 for (int k = 0; k < 4; ++k) {
36 int nr = r + dr[k];
37 int nc = c + dc[k];
38 if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
39 grid[nr][nc] = 2; // rot it
40 freshCount--;
41 q.push({nr, nc});
42 }
43 }
44 }
45 minutes++;
46 }
47
48 return freshCount == 0 ? minutes : -1;
49 }
50};
51
52int main() {
53 Solution sol;
54 std::vector<std::vector<int>> grid = {
55 {2, 1, 1},
56 {1, 1, 0},
57 {0, 1, 1}
58 };
59 std::cout << "Canonical Multi-Source BFS: " << sol.orangesRotting(grid) << " (Expected: 4)\n";
60 return 0;
61}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Round-by-Round Grid SimulationO((m * n)^2)O(m * n)Scans whole grid each minute and copies next state until stable.Repeated full-grid scans
2.Multi-Source BFS with Distance MatrixO(m * n)O(m * n)Tracks exact rot minute in an auxiliary dist matrix.Matrix allocation
3.Canonical Multi-Source BFS with Level ChunkingOptimalO(m * n)O(m * n)Live freshCount decrement and queue size batching.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Incrementing minutes even when no fresh oranges were rotted during the current layer.

Pitfall 2:

Forgetting to return 0 when there are no fresh oranges in the grid at the beginning.

Pitfall 3:

Using DFS instead of BFS: DFS explores one deep path sequentially rather than simulating parallel simultaneous rot spread.

Crucial Edge Cases to Validate:

  • No fresh oranges initially (grid has only 0s and 2s) — freshCount == 0 check immediately returns 0.
  • Fresh orange completely surrounded by empty cells (0s) — Cannot be reached by any rotten orange; freshCount remains > 0, returns -1.
  • No rotten oranges initially, but fresh oranges exist — Queue is empty at start, freshCount > 0, returns -1 immediately.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State immediately: 'This is a multi-source BFS because all rot events occur simultaneously in lockstep per minute.'
  2. Explain why tracking freshCount live is better than a full O(m * n) scan at the end.
  3. Be sure to emphasize the condition freshCount == 0 as an early termination check.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does Rotting Oranges require Multi-Source BFS rather than running Single-Source BFS from each rotten orange separately?

2.What should the algorithm return if the input grid has 0 fresh oranges initially (freshCount == 0)?

3.Why is the while loop condition while (!q.empty() && freshCount > 0) preferred over while (!q.empty())?

Back to DSA Sheet