Approach Summary
Multi-source BFS starting from all rotten oranges simultaneously. Count BFS levels (minutes).
Full Solution & Approach
All rotten oranges spread simultaneously, one cell per minute — that is exactly a multi-source BFS where the level count equals the elapsed minutes. Seed the queue with every initially rotten orange and count the fresh ones. Process the queue level by level: for each rotten orange at the current level, rot its four-directional fresh neighbors, add them to the next level, and decrement the fresh count. Track the number of levels processed as minutes. When the queue empties, if any fresh oranges remain they were unreachable (separated by empty cells) — return -1. Otherwise return the minute count, or 0 if there were never any fresh oranges. The BFS-levels-as-time trick is the standard way to simulate simultaneous spread, and the same skeleton solves shortest-step problems on grids.
Each cell is enqueued at most once — O(m × n) time. The queue holds at most the frontier of rotten cells — O(m × n) worst case.
Solution Code
Solution
def oranges_rotting(grid: list[list[int]]) -> int:
from collections import deque
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
minutes = 0
while queue and fresh:
minutes += 1
for _ in range(len(queue)):
i, j = queue.popleft()
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 2
fresh -= 1
queue.append((ni, nj))
return minutes if fresh == 0 else -1function orangesRotting(grid) {
const m = grid.length, n = grid[0].length;
const queue = [];
let fresh = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] === 2) queue.push([i, j]);
else if (grid[i][j] === 1) fresh++;
}
}
let minutes = 0;
while (queue.length && fresh) {
minutes++;
const size = queue.length;
for (let k = 0; k < size; k++) {
const [i, j] = queue.shift();
for (const [di, dj] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const ni = i + di, nj = j + dj;
if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] === 1) {
grid[ni][nj] = 2;
fresh--;
queue.push([ni, nj]);
}
}
}
}
return fresh === 0 ? minutes : -1;
}public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Deque<int[]> queue = new ArrayDeque<>();
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++;
}
int minutes = 0;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!queue.isEmpty() && fresh > 0) {
minutes++;
int size = queue.size();
for (int s = 0; s < size; s++) {
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;
fresh--;
queue.offer(new int[]{ni, nj});
}
}
}
}
return fresh == 0 ? minutes : -1;
}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++;
}
int minutes = 0;
int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
while (!q.empty() && fresh > 0) {
minutes++;
int size = q.size();
for (int s = 0; s < size; s++) {
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;
fresh--;
q.push({ni, nj});
}
}
}
}
return fresh == 0 ? minutes : -1;
}Edge Cases to Watch
- No fresh oranges at the start — return 0
- A fresh orange isolated by empty cells — return -1
- A single rotten orange in a large grid — minutes equal the longest distance
- Empty grid — return 0
How to Recognize This Pattern
- Simultaneous spread from multiple sources
- BFS levels = time
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)