Rotting Oranges · DSA Prep

This is the same “spread from multiple sources simultaneously” idea as Walls and Gates: every rotten orange is a starting point, and they all decay their neighbors in lockstep, minute by minute. That “all at once, one layer per minute” behavior is exactly what a multi-source BFS gives for free. (The shared GridVisualizer only understands binary 0/1 grids, so this problem owns a small folder-local visualizer that can express all three states — 0 empty, 1 fresh, 2 rotten — plus each cell’s minute stamp and the live BFS queue.)

Brute-Force Minute-by-Minute Simulation

Time O((m·n)²)Space O(m·n)

Directly simulate the process: each minute, look at every currently-rotten orange and rot its fresh neighbors, then advance the clock. Stop when there are no fresh oranges left, or when a full pass rots nothing (meaning some fresh oranges are unreachable).

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])

        def fresh_exists():
            return any(grid[r][c] == 1 for r in range(rows) for c in range(cols))

        minutes = 0
        while fresh_exists():
            rotten_now = [
                (r, c) for r in range(rows) for c in range(cols) if grid[r][c] == 2
            ]
            to_rot = set()
            for r, c in rotten_now:
                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:
                        to_rot.add((nr, nc))
            if not to_rot:
                return -1  # a full pass rotted nothing, but fresh oranges remain
            for nr, nc in to_rot:
                grid[nr][nc] = 2
            minutes += 1
        return minutes

Why it’s correct: each pass rots exactly the fresh oranges adjacent to this minute’s rotten set, matching the problem’s simultaneous-spread rule. Complexity: each of the up to O(m·n) minutes re-scans the whole grid to find the current rotten set → O((m·n)²) time in the worst case (e.g. a single line of oranges rotting one per minute), O(m·n) space for the per-minute sets.

Multi-Source BFS With Time-Stamped Queue

OptimalTime O(m·n)Space O(m·n)

Seed a BFS queue with every rotten orange at time 0. Process the queue once; each time a fresh orange is rotted, push it with time + 1. The answer is the largest timestamp ever popped, as long as no fresh oranges are left unvisited.

from collections import deque

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, 0))
                elif grid[r][c] == 1:
                    fresh += 1

        minutes = 0
        while queue:
            r, c, t = queue.popleft()
            minutes = max(minutes, t)
            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, t + 1))

        return minutes if fresh == 0 else -1

Tracing [[2,1,1],[1,1,0],[0,1,1]] (queue seeded with the single rotten orange at (0,0), time 0) — watch the infection spread one ring per minute: each pop rings the orange being drained, its fresh neighbors flip to rose stamped with their minute, and the counter only climbs when a new minute layer of the spread begins.

minute0fresh6

Queue · next pop first

empty — nothing left to pop

1 / 10

rotten orangefresh orangeempty cellpopped right nowt=2minute it turned rotten

The grid to trace: one rotten orange at `(0,0)`, six fresh oranges, and two empty cells (`(1,2)` and `(2,0)`) that take no part in the spread. Every step below shows the minutes clock, the fresh-orange count, and the BFS queue draining in FIFO order.

The queue empties with fresh = 0 and the largest minute stamp is 4, matching the expected output. Cell (1,2) in the input is 0 (empty), so it plays no part in the spread; the orange at (2,2) is reached the long way around, via (0,0) -> (1,0) -> (1,1) -> (2,1) -> (2,2), which is why it takes the full 4 minutes.

Why it’s correct: BFS from all rotten oranges at once expands one ring of “adjacent to something already rotten” per minute, which matches the problem’s simultaneous-decay rule exactly, and the timestamp on each queue entry is precisely the minute it turns rotten. If any fresh orange is never dequeued, it was unreachable, hence -1. Complexity: every cell enters the queue at most once and does O(1) work per neighbor → O(m·n) time, O(m·n) space for the queue in the worst case — a clean improvement over re-scanning the whole grid every minute.