Rotting Oranges
You're given an m x n grid where each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, any fresh orange directly above, below, left or right of a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange is left. If some fresh orange can never rot, return -1. If there are no fresh oranges to begin with, return 0.
Examples
grid = [[2,1,1],[1,1,0],[0,1,1]] returns 4
Using (row, col): (0,1) and (1,0) rot at minute 1, (0,2) and (1,1) at minute 2, (2,1) at minute 3 and (2,2) at minute 4. The bottom-right orange is the last to turn, so the answer is 4.
grid = [[2,1,1],[0,1,1],[1,0,1]] returns -1
The orange at (2,0) has an empty cell above it and an empty cell to its right, and nothing else touches it. The rot can never reach it, so the answer is -1.
grid = [[0,2]] returns 0
There are no fresh oranges at the start, so no time needs to pass.
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2.
Hints
Picture each cell as linked to its 4 neighbors. The minute an orange rots equals how many steps it sits from the nearest rotten orange.
Use a multi-source breadth-first search: put every rotten orange in the queue before you start, and treat each BFS layer as one minute.
Queue all rotten cells and count the fresh ones. While the queue is non-empty and fresh > 0, add a minute, then pop exactly the current layer, turning each fresh neighbor to 2, decrementing fresh and enqueueing it. Return minutes if fresh is 0, else -1.
Drill This: Your Approach First
Approach
Every rotten orange spreads at the same time, so seed a queue with all of them at once and count the fresh oranges. Then run breadth-first search one layer per minute: pop the whole current layer, rot each fresh neighbor and enqueue it. An orange rots in the layer equal to its distance from the nearest rotten orange, which is exactly its rot time. Stop once the fresh count hits 0 and return the minutes, or -1 if the queue empties first.
Time
O(m * n)
Space
O(m * n)
Pitfall
Solutions
class Solution {
public int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
Deque<int[]> queue = new ArrayDeque<>();
int fresh = 0;
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) queue.offer(new int[]{r, c});
else if (grid[r][c] == 1) fresh++;
}
}
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int minutes = 0;
while (!queue.isEmpty() && fresh > 0) {
minutes++;
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
fresh--;
queue.offer(new int[]{nr, nc});
}
}
}
}
return fresh == 0 ? minutes : -1;
}
}from collections import deque
from typing import List
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue and fresh > 0:
minutes += 1
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2
fresh -= 1
queue.append((nr, nc))
return minutes if fresh == 0 else -1