Rotten Oranges
Rotten oranges rot their 4-neighbours each minute. Return minutes until all rot, or −1 if some never do.
Open on LeetCode ↗Intuition
Rot spreads like a wave from every rotten orange at once — that's a multi-source BFS. Seed the queue with all initially rotten cells; each BFS layer is one minute. Fresh oranges the wave never reaches → −1.
Multi-source BFS. Every rotten orange starts in the queue at time 0, so the wave spreads from all of them simultaneously and the last node dequeued carries the answer. Whenever a spread happens from several starting points at once, seed them all rather than running BFS once per source.
Approach
Seed all sources at once
Push every rotten cell with time 0 and count the fresh ones. Multi-source BFS is just BFS with many starting points.
Layer = minute
Process the queue; a fresh neighbour rots at parent time + 1. BFS guarantees each orange is reached at its earliest possible minute.
Check completeness
If fresh count hits 0, the last rot time is the answer; otherwise some orange was unreachable → −1.
Solution & live demo
Common pitfalls
Running BFS from each rotten orange separately
for each rotten: bfs(...) return max(times)
for r, c in all rotten: q.append((r, c, 0))
Separate runs cost O(sources × cells) and need a per-cell minimum across runs to be correct. Seeding every source at time 0 makes one pass compute the true simultaneous spread.
Not checking for unreachable fresh oranges
return t
return t if fresh == 0 else -1
Fresh oranges walled off from any rotten one never rot, and the answer must be −1. Tracking the fresh count and verifying it hits zero is what distinguishes "finished" from "stalled".
Marking cells rotten only when dequeued
r, c, t = q.popleft() grid[r][c] = 2
grid[nr][nc] = 2 q.append((nr, nc, t + 1))
A cell reachable from two rotten neighbours gets enqueued twice before either is processed, so it's counted twice and can be assigned a later time. Marking at enqueue time makes each cell enter the queue exactly once.
Edge cases
Answer 0 — nothing to wait for.
Never enqueued; fresh count stays positive → −1.