• m == grid.length, n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2
• Rotting spreads only up, down, left and right — never diagonally.
• Empty cells block the spread; rot cannot cross them.

Read the rule carefully: every fresh orange next to a rotten one turns rotten within the same minute, and all of this happens at once. So the process is not a chain of individual events — it is a whole layer of the grid flipping state, then the next layer, then the next. The question asks how many layers it takes to consume everything.

That should immediately suggest a picture of fronts advancing in step. The job is to make that picture into an algorithm without accidentally letting one front run ahead of another.

The most direct translation of the rules: loop once per minute, and on each pass scan the entire grid, marking every fresh orange that currently touches rot.

def oranges_rotting(grid):
    minutes = 0
    while True:
        newly_rotten = []
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 1 and touches_rot(grid, r, c):
                    newly_rotten.append((r, c))
        if not newly_rotten:
            break
        for r, c in newly_rotten:
            grid[r][c] = 2          # apply all at once, AFTER the scan
        minutes += 1
    return minutes if no_fresh_left(grid) else -1

This is correct, and the two-phase structure is not optional: if you flipped cells to 2 during the scan itself, a cell rotted this minute could infect its neighbour in the very same pass, and rot would race across the grid far too fast. Collecting first and applying afterwards is what enforces simultaneity.

Correct, but wasteful, and the waste has a precise shape. Each minute rescans all m × n cells, but almost all of them are irrelevant — empty cells, long-rotten oranges, and fresh oranges nowhere near the action. Only the cells adjacent to those that rotted last minute can possibly change. With up to m × n minutes and a full scan each time, the cost is O((m × n)²).

Name the waste exactly: we keep searching the grid for the frontier, when we could have simply remembered it.

Keep a list of the oranges that rotted during the previous minute. Those are the only cells capable of infecting anything now. Process exactly those, collect whatever they infect, and that collection becomes the next minute's frontier. The grid is never scanned again after the initial setup.

Two consequences fall out. First, each cell is touched a constant number of times overall, so the whole simulation is linear in the grid size. Second, and more interesting: the number of frontier generations is the answer. Time is not something you track separately alongside the spread — it is the depth of the spread.

The structure holding the frontier is a queue: add at the back, remove from the front. That FIFO discipline is what keeps generation d fully processed before any of generation d+1 begins. A stack would let one branch race ahead and the minute count would be meaningless. This ring-by-ring expansion is Breadth-First Search, and the version here has a particular twist worth naming.

Ordinary BFS starts from one cell. Here, every initially rotten orange starts spreading at the same instant, so every one of them is seeded into the queue before the loop begins. That is multi-source BFS, and the correctness argument is worth being able to state: with all sources at distance 0, the wave that first reaches any cell came from whichever source is nearest to it, so each cell is claimed at exactly the minute it would truly rot. You get the effect of running a separate search from every rotten orange, at the cost of one.

The impossibility case needs handling too, and there is a neat way to do it: count the fresh oranges during setup and decrement as each one rots. If the counter is not zero when the queue empties, the survivors were unreachable.

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0

    for r in range(rows):                     # setup: seed every source at once
        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)):           # freeze the size: exactly this minute's front
            r, c = queue.popleft()
            for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
                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

The second subtlety is the fresh > 0 condition on the outer loop. Without it, the final generation — the one that infects nothing, because everything is already rotten — would still increment minutes, giving an answer one too large. Stopping the moment the last fresh orange is consumed also handles the no-fresh-oranges grid correctly: the loop never runs and 0 is returned.

Setup visits every cell once, and each orange enters and leaves the queue at most once, so the whole thing is O(m × n) time and O(m × n) memory for the queue.

Setup finds one rotten orange at (0,0), so the queue starts as [(0,0)], and counts 7 fresh oranges — every cell except (0,0), (1,2) and (2,0).

The loop condition now fails and the answer is 4. Notice the rot had to travel around the empty cell at (1,2) rather than through it — the empty cell is why the far corner takes 4 minutes rather than 3.

For [[2,1,1],[0,1,1],[1,0,1]], the spread proceeds normally but (2,0) has an empty cell above at (1,0) and an empty cell beside at (2,1). It is never adjacent to anything rotten, so when the queue drains, fresh is still 1 and the answer is -1.

Two things transfer out of this problem.

The first is multi-source BFS. Whenever many starting points act simultaneously — infections, fires spreading, signals broadcast from several towers, water rising from every coastline — seed all of them into the queue before the loop. You are not running many searches; you are running one search whose distance-0 layer happens to have many members. It costs the same as a single-source search and answers "distance to the nearest source" for every cell in the grid at once.

The second is the identification of time with layer depth. The moment a problem's rules say "each step, everything adjacent changes", the number of steps is the number of BFS generations, and the frozen-size loop is how you count them. That pattern recurs directly in problems about infection times in trees and about how long it takes a signal to reach every node in a network.

Train the reflex: when a statement says many things spread at once and asks how long until everything is covered, do not simulate one spreader at a time and do not rescan the world each tick. Seed every source into one queue and count generations.