Description
A grid contains empty cells (0), fresh oranges (1), and rotten oranges (2). Each minute, rotten oranges spoil adjacent fresh oranges. Return minutes until none are fresh, or -1 if some cannot be reached.
Solution
from collections import deque
def oranges_rotting(grid):
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:
for _ in range(len(queue)):
r, c = queue.popleft()
for x, y in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
if 0 <= x < rows and 0 <= y < cols and grid[x][y] == 1:
grid[x][y] = 2
fresh -= 1
queue.append((x, y))
minutes += 1
return minutes if fresh == 0 else -1Examples
Example 1
- Input
[[[2,1,1],[1,1,0],[0,1,1]]]- Output
4
The farthest orange spoils after four waves.
Example 2
- Input
[[[2,1,1],[0,1,1],[1,0,1]]]- Output
-1
The lower-left fresh orange is isolated.
Example 3
- Input
[[[0,2]]]- Output
0
There are no fresh oranges.
Approach
Start a breadth-first search from all rotten oranges at once. Process one frontier per minute and track the fresh count. Stop when it reaches zero or the frontier cannot expand.
Time & space
O(rc) time and O(rc) auxiliary space, where r and c are grid dimensions. The grid is marked in place.