Rotting Oranges

Find how many minutes all reachable fresh oranges need to rot.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Rotting Oranges: Seeding every rotten cell makes BFS time equal the shortest orthogonal distance from any source; the last timestamp is the required minute.

Input and goalFind how many minutes all reachable fresh oranges need to rot.

Seed every time-zero sourceIn [[2,1,1],[1,1,0],[0,1,1]], enqueue (0,0,0) and count 6 fresh oranges. Here 2 = rotten, 1 = fresh, and 0 = empty.

2frontier t=011110011

queueState[(0,0,0)]fresh6minute0

Recognize it

Use multi-source BFS for simultaneous unweighted spreading, infection, nearest-source distance, or minimum elapsed steps when every source acts at time zero and each move has equal cost.

Keep true

When (row,col,time) is popped, time is its minimum distance from any initial rotten cell. Marking a fresh neighbor rotten before enqueueing ensures that cell is queued once at time + 1.

Reuse it

Seed all equal-priority sources before BFS, mark neighbors when enqueued, and carry distance in the queue; the same mechanism solves nearest gate, fire spread, and shortest distance to any facility.

Pattern: Multi-source BFS.

Simple idea: Every rotten orange starts spreading at time 0. Put all of them in the queue before BFS. Each queue level is one minute.

from collections import deque

def rotting_oranges(grid: list[list[int]]) -> int:
   if not grid or not grid[0]:
      return 0

   queue = deque(
      (row, col, 0)
      for row in range(len(grid))
      for col in range(len(grid[0]))
      if grid[row][col] == 2
   )
   fresh = sum(cell == 1 for row in grid for cell in row)

   minutes = 0
   while queue:
      row, col, minutes = queue.popleft()
      for row_step, col_step in ((1, 0), (-1, 0), (0, 1), (0, -1)):
         new_row = row + row_step
         new_col = col + col_step
         if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[0]):
            if grid[new_row][new_col] == 1:
               grid[new_row][new_col] = 2
               fresh -= 1
               queue.append((new_row, new_col, minutes + 1))

   return minutes if fresh == 0 else -1

Cost: $O(rows\times cols)$ time and space.