The machine must simulate rotting spreading through a grid: each minute, every rotten orange infects its four edge-adjacent fresh neighbors. The answer is the minutes until all fresh oranges rot, or -1 if some fresh orange is forever isolated from rot.
The key insight is that all rotten oranges spread simultaneously, which is exactly what a multi-source BFS models. Seeding the queue with every rotten orange and counting BFS layers gives the elapsed minutes directly.
The approach has three steps. First, scan the grid, enqueue every rotten orange, and count fresh ones. Second, run BFS layer by layer: pop the whole frontier, infect fresh neighbors, decrement the fresh count, and enqueue newly rotten cells, counting one minute per layer. Third, when the queue empties, return the minutes if no fresh oranges remain, otherwise -1. Every cell is processed once, so time and space are O(rows × cols).
The trickiest edge case is a grid with no fresh oranges: the answer is 0 minutes, and the machine must not report -1 just because the queue starts empty. The fresh-orange counter distinguishes "everything rotted" from "a fresh orange is unreachable."
from collections import deque
def orangesRotting(grid):
rows, cols = len(grid), len(grid[0])
q = deque()
fresh = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
q.append((r, c))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while q and fresh:
for _ in range(len(q)):
r, c = q.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
q.append((nr, nc))
minutes += 1
return minutes if fresh == 0 else -1