Rotting Oranges

mediumTests passed 2026-11-11v1.0.0
TC: O(M * N)|SC: O(M * N)
GraphsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Seed one **multi-source BFS** queue simultaneously with ALL initially rotten cells (`2`) while counting `fresh` cells (`1`). Process level-by-level while `q and fresh > 0`, decrementing `fresh` on each rot.

2. Complexity Bounds & Proof

Every fresh cell enters the BFS queue at most once in exact shortest-path wavefront order.

3. Minimal Idiomatic Code

def orangesRotting(grid: list[list[int]]) -> int:
    R, C = len(grid), len(grid[0])
    q = deque()
    fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                q.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    mins = 0
    while q and fresh > 0:
        mins += 1
        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 < R and 0 <= nc < C and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
    return mins if fresh == 0 else -1

4. Failure Modes & Interview Follow-ups

Pitfalls:- Incrementing `minutes` even on the final wave when `fresh == 0` overcounts by 1 minute (guard loop with `while q and fresh > 0`). - Returning `-1` when `fresh == 0` initially.
Follow-ups:- Walls and Gates is identical multi-source BFS seeded from all gates (`0`).

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Number of Islands (O(M * N))Pacific Atlantic Water Flow (O(M * N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.