Rotting Oranges
Description
You are given an m × n grid where each cell holds one of three integer values:
- 0 — the cell is empty (no orange)
- 1 — the cell contains a fresh orange
- 2 — the cell contains a rotten orange
Every minute, any fresh orange that is 4-directionally adjacent (up, down, left, or right) to a rotten orange also becomes rotten.
Return the minimum number of minutes that must elapse until no fresh orange remains in the grid. If it is impossible for every fresh orange to become rotten, return -1.
Examples
Example 1
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: The rotten orange at position (0,0) begins spreading. At minute 1 it rots (0,1) and (1,0). At minute 2 the newly rotten oranges rot (0,2) and (1,1). At minute 3, (1,1) rots (2,1). Finally at minute 4, (2,1) rots (2,2). All fresh oranges are now rotten after 4 minutes.
Example 2
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The rotten orange at (0,0) eventually rots the oranges it can reach, but the fresh orange at (2,0) is surrounded by empty cells and can never be reached by any rotten orange. Therefore we return -1.
Example 3
Input: grid = [[0,2]]
Output: 0
Explanation: There are no fresh oranges at all, so zero minutes are needed. We return 0 immediately.
Constraints
- m == grid.length
- n == grid[i].length
- 1 ≤ m, n ≤ 10
- grid[i][j] is 0, 1, or 2
Editorial
Brute Force - Repeated Grid Scanning
Intuition
The most straightforward way to simulate the rotting process is to repeatedly scan the entire grid. In each pass we look at every cell: whenever we find a rotten orange, we check its four neighbours and mark any adjacent fresh orange for rotting.
The key subtlety is that oranges rotted during the current minute should not be allowed to rot their own neighbours in that same minute — they only start spreading in the next pass. To handle this we work on a copy of the grid: we read from the original and write changes to the copy, then replace the original with the copy at the end of the pass.
We keep repeating passes, incrementing a minute counter each time, until a full scan produces no changes. At that point, if any fresh orange still exists the answer is -1; otherwise the counter holds our answer.
Think of it like a teacher walking through rows of seats checking homework. Each complete walk through the room is one 'minute'. If a seat next to an already-checked wrong answer gets infected with the wrong approach, it only counts in the next full walk-through, not the current one.
Step-by-Step Explanation
Let's trace through grid = [[2,1,1],[1,1,0],[0,1,1]]:
Step 1: Initial state — one rotten orange at (0,0), six fresh oranges at (0,1), (0,2), (1,0), (1,1), (2,1), (2,2), and two empty cells at (1,2) and (2,0).
Step 2: Pass 1 — scan every cell. Find (0,0) is rotten. Check its right neighbour (0,1): fresh → mark for rotting. Check its down neighbour (1,0): fresh → mark for rotting. Up and left are out of bounds. No other rotten cells exist yet.
Step 3: Apply pass 1 changes. Grid becomes [[2,2,1],[2,1,0],[0,1,1]]. Time = 1 minute. Changes occurred, so continue.
Step 4: Pass 2 — scan again. (0,1) is rotten: right (0,2) is fresh → mark. Down (1,1) is fresh → mark. (1,0) is rotten: right (1,1) already being marked, down (2,0) is empty.
Step 5: Apply pass 2 changes. Grid becomes [[2,2,2],[2,2,0],[0,1,1]]. Time = 2 minutes.
Step 6: Pass 3 — (1,1) is rotten: down (2,1) is fresh → mark. No other new changes.
Step 7: Apply pass 3 changes. Grid becomes [[2,2,2],[2,2,0],[0,2,1]]. Time = 3 minutes.
Step 8: Pass 4 — (2,1) is rotten: right (2,2) is fresh → mark.
Step 9: Apply pass 4 changes. Grid becomes [[2,2,2],[2,2,0],[0,2,2]]. Time = 4 minutes.
Step 10: Pass 5 — full scan finds no fresh neighbour adjacent to any rotten orange. No changes → stop.
Step 11: Check for remaining fresh oranges — none found. Return 4.
Brute Force — Repeated Grid Scanning — Watch how each full pass over the grid spreads the rot by one layer, requiring a complete scan of every cell before advancing the clock by one minute.
Algorithm
- Set minutes = 0 and define the four direction offsets (up, down, left, right)
- Loop until no changes occur in a full pass:
a. Create a copy of the current grid
b. For every cell (i, j) in the original grid:- If grid[i][j] == 2 (rotten), check all four neighbours
- If a neighbour is in bounds and contains a fresh orange (1), mark it as 2 in the copy and set a changed flag
c. If no changes were made, break out of the loop
d. Replace the grid with the copy and increment minutes
- Scan the grid one final time — if any cell still holds 1, return -1
- Otherwise return minutes
Code
#include <vector>
using namespace std;
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int minutes = 0;
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (true) {
vector<vector<int>> copy(grid);
bool changed = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
for (auto& d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n
&& grid[ni][nj] == 1) {
copy[ni][nj] = 2;
changed = true;
}
}
}
}
}
if (!changed) break;
grid = copy;
minutes++;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) return -1;
return minutes;
}
};class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
minutes = 0
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while True:
copy = [row[:] for row in grid]
changed = False
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
copy[ni][nj] = 2
changed = True
if not changed:
break
grid = copy
minutes += 1
for row in grid:
if 1 in row:
return -1
return minutesclass Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
int minutes = 0;
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (true) {
int[][] copy = new int[m][n];
for (int i = 0; i < m; i++) {
copy[i] = grid[i].clone();
}
boolean changed = false;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
for (int[] d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n
&& grid[ni][nj] == 1) {
copy[ni][nj] = 2;
changed = true;
}
}
}
}
}
if (!changed) break;
grid = copy;
minutes++;
}
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (grid[i][j] == 1) return -1;
return minutes;
}
}Complexity Analysis
Time Complexity: O((m × n)²)
In the worst case the grid forms a long snake-like path where rot can only advance one cell per pass. That means up to O(m × n) passes, and each pass scans every cell, costing O(m × n). Multiplying these gives O((m × n)²).
Space Complexity: O(m × n)
We create a full copy of the grid each pass, which requires O(m × n) extra space.
Why This Approach Is Not Efficient
The brute force scans the entire grid from top-left to bottom-right on every single pass, even though only a small frontier of rotten oranges can actually spread the rot. Most cells are either already rotten, empty, or not yet reachable — scanning them is pure waste.
With the constraints (m, n ≤ 10) the grid is at most 100 cells, so worst-case O(100²) = 10 000 operations is still fast enough. But conceptually the approach is O((m × n)²), which becomes impractical if grids were larger.
Key insight: Instead of scanning every cell to find the rotten ones each pass, we can maintain a collection of the cells that are currently on the frontier. This way we process only the cells that matter. A queue lets us do exactly this: enqueue all initially rotten oranges, then process them level by level. Each level represents one minute, and we only visit neighbours of the current frontier — no wasted scans. This reduces the total work to O(m × n), a single pass over the grid.
Optimal Approach - Multi-Source BFS
Intuition
Imagine dropping a stone into a pond — ripples spread outward in concentric rings. Now imagine dropping several stones at the same time: each creates its own ripple, and the ripples expand simultaneously. The rot in this problem behaves exactly like those ripples.
All initially rotten oranges are the 'stones'. They start spreading at the same time, and each wave of spreading takes one minute. The fresh oranges directly touching a rotten one form the first ring (minute 1). The fresh oranges touching those form the second ring (minute 2), and so on.
This level-by-level expansion is precisely what Breadth-First Search (BFS) does. BFS explores all nodes at distance 1 before moving to distance 2, then distance 3, and so on. By starting BFS from all rotten oranges simultaneously (multi-source BFS), we naturally measure the minimum time for rot to reach every reachable fresh orange.
The algorithm has three phases:
- Setup — scan the grid to find every rotten orange (enqueue it) and count fresh oranges.
- BFS — process the queue level by level. Each level = one minute. For every rotten orange at the current level, check its four neighbours and rot any fresh one, adding it to the queue for the next level.
- Result — if all fresh oranges were rotted (count reaches 0), return the number of levels processed. Otherwise return -1.
Step-by-Step Explanation
Let's trace with grid = [[2,1,1],[1,1,0],[0,1,1]]:
Step 1: Scan the grid. Found rotten orange at (0,0). Count fresh oranges: 6 total at (0,1), (0,2), (1,0), (1,1), (2,1), (2,2). Initialize BFS queue = [(0,0)].
Step 2: Minute 1 begins. Queue size = 1. Dequeue (0,0). Check four neighbours.
Step 3: Right neighbour (0,1) is fresh → rot it (set to 2), enqueue (0,1). Fresh count drops to 5.
Step 4: Down neighbour (1,0) is fresh → rot it, enqueue (1,0). Fresh count = 4. Up and left are out of bounds. Level 1 done.
Step 5: Minute 2 begins. Queue has 2 cells: (0,1) and (1,0). Dequeue (0,1). Check neighbours.
Step 6: Right (0,2) is fresh → rot, enqueue. Fresh = 3.
Step 7: Down (1,1) is fresh → rot, enqueue. Fresh = 2. Left (0,0) already rotten. Done with (0,1).
Step 8: Dequeue (1,0). Up (0,0) already rotten. Right (1,1) just rotted this minute. Down (2,0) is empty. Left is out of bounds. No new rotting from this cell. Level 2 done.
Step 9: Minute 3 begins. Queue has 2 cells: (0,2) and (1,1). Dequeue (0,2). No fresh neighbours — all are rotten or empty or out of bounds.
Step 10: Dequeue (1,1). Down (2,1) is fresh → rot, enqueue. Fresh = 1. Level 3 done.
Step 11: Minute 4 begins. Queue has 1 cell: (2,1). Dequeue (2,1). Right (2,2) is fresh → rot. Fresh = 0.
Step 12: Fresh count = 0. All oranges are rotten. Return 4.
Multi-Source BFS — Level-by-Level Rot Spreading — Watch how BFS processes only the frontier cells at each level, spreading the rot outward like expanding ripples without scanning irrelevant cells.
Algorithm
- Scan the grid:
- For every cell with value 2, add its coordinates to a BFS queue
- For every cell with value 1, increment a fresh orange counter
- If fresh count is 0, return 0 immediately (nothing to rot)
- Set minutes = 0 and define direction offsets for up, down, left, right
- While the queue is not empty AND fresh count > 0:
a. Increment minutes
b. Record the current queue size (this is the level size)
c. For each cell in the current level:- Dequeue a cell (i, j)
- Check all four neighbours (ni, nj)
- If the neighbour is in bounds and contains a fresh orange:
- Set grid[ni][nj] = 2
- Enqueue (ni, nj)
- Decrement fresh count
- If fresh count > 0, return -1 (unreachable oranges exist)
- Otherwise return minutes
Code
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
queue<pair<int, int>> q;
int fresh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) q.push({i, j});
else if (grid[i][j] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int minutes = 0;
int dirs[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (!q.empty() && fresh > 0) {
minutes++;
int sz = q.size();
for (int k = 0; k < sz; k++) {
auto [i, j] = q.front();
q.pop();
for (auto& d : dirs) {
int ni = i + d[0], nj = j + d[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n
&& grid[ni][nj] == 1) {
grid[ni][nj] = 2;
q.push({ni, nj});
fresh--;
}
}
}
}
return fresh > 0 ? -1 : minutes;
}
};from collections import deque
class Solution:
def orangesRotting(self, grid: list[list[int]]) -> int:
m, n = len(grid), len(grid[0])
queue = deque()
fresh = 0
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j))
elif grid[i][j] == 1:
fresh += 1
if fresh == 0:
return 0
minutes = 0
dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while queue and fresh > 0:
minutes += 1
for _ in range(len(queue)):
i, j = queue.popleft()
for di, dj in dirs:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 2
queue.append((ni, nj))
fresh -= 1
return -1 if fresh > 0 else minutesimport java.util.*;
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) queue.offer(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
}
if (fresh == 0) return 0;
int minutes = 0;
int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while (!queue.isEmpty() && fresh > 0) {
minutes++;
int sz = queue.size();
for (int k = 0; k < sz; k++) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int ni = cell[0] + d[0], nj = cell[1] + d[1];
if (ni >= 0 && ni < m && nj >= 0 && nj < n
&& grid[ni][nj] == 1) {
grid[ni][nj] = 2;
queue.offer(new int[]{ni, nj});
fresh--;
}
}
}
}
return fresh > 0 ? -1 : minutes;
}
}Complexity Analysis
Time Complexity: O(m × n)
The initial grid scan to find rotten oranges and count fresh ones takes O(m × n). During BFS, each cell is enqueued and dequeued at most once because a fresh orange is set to 2 immediately upon discovery, preventing re-processing. For each dequeued cell we check at most 4 neighbours — constant work. So the BFS portion is also O(m × n). Total: O(m × n).
Space Complexity: O(m × n)
In the worst case every cell could be a rotten orange initially, meaning all m × n cells are enqueued at the start. The queue therefore requires O(m × n) space. No additional grid copy is needed because we modify the input grid in place.