Lab 03 — Multi-Source BFS (Rotting Oranges)

Goal

Implement multi-source BFS on a grid to compute the minimum time for a process to spread from multiple simultaneous starting points. After this lab you should be able to recognize the multi-source BFS signal (any “infection / spread / nearest-source” problem) in <60 seconds, initialize the queue correctly with all sources at distance 0, and write the layer-by-layer time-tracking logic without off-by-ones.

Background Concepts

Multi-source BFS is single-source BFS with a virtual super-source connected to all real sources by zero-weight edges. We don’t materialize the super-source; we just enqueue all real sources at distance 0 simultaneously. The BFS then proceeds layer by layer, and each cell’s distance is min over all sources of (path length to that source). Critically, this is O(V + E) — same as single-source BFS — not O(K · (V + E)) for K sources.

The “rotting oranges” problem asks: given a grid where some cells contain rotten fruit (sources) and some contain fresh fruit (targets), how many time steps until all fresh fruit rots? Each minute, every rotten orange infects its 4-connected fresh neighbors. The answer is the maximum BFS distance among fresh oranges, or -1 if any fresh orange is unreachable.

Interview Context

Rotting Oranges (LC 994) appears at Amazon, Meta, and Microsoft phone screens regularly. The trap is candidates running single-source BFS K times — one per rotten cell — which is O(K · R · C) and blows up at K = R · C / 2. Multi-source BFS is the senior signal here; recognizing it within the first 90 seconds and stating it explicitly differentiates a strong L4 from a struggling one.

Problem Statement

Given an m × n grid where each cell is:

  • 0: empty,
  • 1: fresh orange,
  • 2: rotten orange,

each minute every rotten orange rots its 4-connected fresh neighbors. Return the minimum minutes until no fresh orange remains, or -1 if some fresh orange can never rot.

Constraints

  • 1 ≤ m, n ≤ 10
  • grid[i][j] ∈ {0, 1, 2}
  • (Note: small grid in LC 994; the algorithm scales to 10^4 × 10^4 trivially.)

Clarifying Questions

  1. If the grid has no fresh oranges initially, what’s the answer? (0 — already done.)
  2. If a rotten orange has no fresh neighbors and there are no fresh oranges anywhere, return 0. If there are unreachable fresh oranges, return -1.
  3. Are ties between sources broken consistently? (Doesn’t matter — we want minimum distance, which is unambiguous.)
  4. Can a rotten orange “re-rot” a previously-rotted cell? (No — once rotten, stays rotten.)

Examples

grid = [[2,1,1],
        [1,1,0],
        [0,1,1]]
→ 4

grid = [[2,1,1],
        [0,1,1],
        [1,0,1]]
→ -1  (bottom-left is unreachable)

grid = [[0,2]]
→ 0

Initial Brute Force

Simulate minute by minute: at each step, find every rotten orange, infect its fresh neighbors, count rotted cells. Repeat until no change. Each step is O(R · C); total steps ≤ R + C; total O((R + C) · R · C) — at 10 × 10 trivially fast, but doesn’t scale.

Brute Force Complexity

O(R · C · max-distance). At 10 × 10, ~10^4 ops. Passes LC bounds easily but is “embarrassing” — interviewer wants the BFS framing.

Optimization Path

Multi-source BFS gives the optimal O(R · C):

  1. Scan grid: count fresh oranges; enqueue every rotten orange at distance 0.
  2. BFS layer by layer; on rotting a fresh cell, decrement the fresh count and enqueue at next distance.
  3. After BFS, if fresh count > 0, return -1; else return the maximum distance reached.

The simulation is mathematically equivalent but presents better in interviews — it’s the canonical multi-source signal.

Final Expected Approach

fresh_count = count of '1' in grid
queue = deque of (r, c, 0) for every '2' in grid
time = 0
while queue:
    r, c, t = queue.popleft()
    time = max(time, t)
    for each 4-neighbor (nr, nc):
        if in bounds and grid[nr][nc] == 1:
            grid[nr][nc] = 2
            fresh_count -= 1
            queue.append((nr, nc, t + 1))
return -1 if fresh_count > 0 else time

Data Structures Used

  • collections.deque of (row, col, time) tuples.
  • The input grid as the visited marker (mutate fresh → rotten on rot).
  • An integer fresh_count.

Correctness Argument

The super-source argument: imagine a virtual node S₀ connected to every initial rotten cell by a zero-weight edge. BFS from S₀ visits cells in non-decreasing distance order; each cell’s distance is 1 + min over rotten cells of (path length). By initializing with all rotten cells at distance 0 instead, we get the same distances. The “minutes until no fresh remains” equals the maximum BFS distance among initially-fresh cells; this is exactly the time the last cell rots. Unreachable fresh cells are detected by the fresh_count > 0 check post-BFS.

Complexity

OperationTimeSpace
Initial scanO(R · C)O(R · C) for queue worst case
BFSO(R · C)(already counted)
TotalO(R · C)O(R · C)

Implementation Requirements

from collections import deque

def orangesRotting(grid):
    R, C = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh += 1
    if fresh == 0:
        return 0
    DIRS = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    time = 0
    while queue:
        r, c, t = queue.popleft()
        time = t
        for dr, dc in DIRS:
            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
                queue.append((nr, nc, t + 1))
    return -1 if fresh > 0 else time

Tests

  • All rotten: 0.
  • All fresh, no rotten: -1.
  • Mixed with one isolated fresh: -1.
  • Single rotten in corner, all fresh: distance = R + C - 2.
  • Empty grid (all zeros): 0.
  • 1×1 grid with [[0]]: 0; [[1]]: -1; [[2]]: 0.
  • Stress: 10×10 random; verify against simulation brute force.

Follow-up Questions

  1. “What if rotting takes a different amount of time per cell?” → Edge weights vary; use Dijkstra.
  2. “What if there are obstacle cells?” → Add grid[nr][nc] == 0 skip; same algorithm.
  3. “What if oranges can only rot orthogonally to one direction?” → Replace DIRS with the allowed subset.
  4. “Walls and Gates (LC 286): from each empty room, find distance to nearest gate.” → Same multi-source BFS pattern; gates are the sources.
  5. “01 Matrix (LC 542): for each cell, distance to nearest 0.” → Sources are the 0s; targets are the 1s.

Product Extension

Spreadable processes — disease propagation in epidemiology, fire spread in simulations, viral content propagation in social graphs, “blast radius” of a deployment failure across a service mesh — all map to multi-source BFS. The minute-by-minute simulation in production tracking systems is exactly this algorithm.

Language/Runtime Follow-ups

  • Python: collections.deque is the canonical queue. Tuples for (r, c, t). Avoid list.pop(0) — that’s O(N).
  • Java: ArrayDeque<int[]> with int[]{r, c, t}. Use pollFirst / offerLast.
  • Go: a slice as queue (q[1:] is O(1) amortized, or use container/list). A [3]int struct is fine.
  • C++: queue<tuple<int,int,int>>. emplace for efficiency. auto [r, c, t] = q.front() in C++17.
  • JS/TS: array shift() is O(N) — use a deque or pointer-based queue. queueMicrotask is irrelevant here.

Common Bugs

  1. Counting time as time + 1 after the BFS terminates — the last layer’s t is already correct.
  2. Forgetting to enqueue all rotten cells before starting — single-source BFS, missing K-1 sources.
  3. Initializing time to -1 vs 0 to handle the “no fresh” case — corner case.
  4. Decrementing fresh_count too late, double-decrementing on revisits.
  5. BFS correctly terminating but reporting t from the wrong layer (e.g., the last enqueued, not last popped).
  6. Mutating 1 to 2 outside the bounds check.
  7. Mistaking the answer “minutes” for “max steps” when the grid has no fresh oranges (answer is 0, not “the BFS terminates immediately”; you must short-circuit).

Debugging Strategy

Trace a 3 × 3 grid by hand: print the queue contents and grid after each pop. Verify time increments by exactly 1 between layers. If fresh > 0 at the end, identify the unreachable cell — confirm it has no path to any source by visual inspection. If time is off by 1, you’re probably tracking time = t + 1 on enqueue instead of t on pop.

Mastery Criteria

  • Recognized “spread from multiple sources” as multi-source BFS in <60 seconds.
  • Initialized the queue with all sources at distance 0 unprompted.
  • Wrote correct BFS with time tracking from cold start in <8 minutes.
  • Stated O(R · C) complexity unprompted; explained why running K single-source BFSs is wrong.
  • Solved LC 994 in <12 minutes from cold start.
  • Solved LC 286 (Walls and Gates) in <12 minutes by extending the template.
  • Solved LC 542 (01 Matrix) in <12 minutes.
  • Articulated the super-source equivalence in <30 seconds.