rotting-oranges

Difficulty: Medium · Topic: Graphs · Practice it on parikshan: /practice/rotting-oranges/start

The story

A produce wholesaler runs cold-storage racks. Sensors detect rotten oranges; the operations team wants a model that tells them, given the current state of a rack, how many minutes until every orange is spoiled (so they can choose between accelerated sale, animal feed, or compost) and whether any orange is stranded behind empty cells (so it can be flagged for inspection before it becomes a sanitation issue).

This is rotting-oranges. The same algorithm runs fire-spread simulations in wildfire response, contagion models in public health, propagation analytics in social networks, and "spread of bad input" in software-fault propagation models. Whenever a process spreads from multiple sources at the same rate, this is the algorithm.

What's actually being asked

You have a grid of r × c cells. Each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, each fresh orange that is 4-neighbour-adjacent to a rotten orange becomes rotten. Print the minimum number of minutes until no fresh oranges remain, or -1 if some fresh orange is unreachable. If the tray starts with no fresh oranges, print 0.

The naive approach

Simulate the minutes one by one. Each minute, scan the entire grid, mark fresh cells adjacent to rotten cells, increment the counter. Repeat until nothing changes. Time is O(minutes · r · c). On a 200x200 grid with a single seed in one corner, "minutes" can hit 400. That is 16 million ops, which is fine, but the pattern is wasteful: every minute re-scans cells that have not changed in the last 100 minutes.

The right framing makes the inefficiency vanish.

The key insight

This is a shortest-path problem in disguise. The minute a fresh cell becomes rotten equals its 4-neighbour graph distance to the nearest rotten cell in the initial grid. The answer is the maximum such distance across all fresh cells. Compute it with one BFS, not 400.

The trick is the seeding. BFS from a single source gives you distance to that source. BFS from many sources, all seeded with distance 0 before the first pop, gives you distance to the nearest source. That second pattern is called multi-source BFS, and it is exactly the right tool here.

The unreachable-orange case is detected by counting fresh oranges up front and decrementing every time a fresh cell rots. After the BFS, if the counter is positive, the answer is -1.

Step-by-step approach

Scan the grid once. Build a deque seeded with every initial '2' cell paired with timestamp 0. Count the fresh oranges into fresh.
Initialise minutes = 0.
BFS:
- Pop (x, y, t). Update minutes = max(minutes, t).
- For each 4-neighbour (nx, ny) in bounds:
  - If grid[nx][ny] == '1': set it to '2', decrement fresh, enqueue (nx, ny, t + 1).
After the BFS: print -1 if fresh > 0; otherwise print minutes.

The mark-on-enqueue (set to '2' the moment you push) doubles as the visited check: the next time anyone examines that cell, it is no longer '1', so the if-test rejects it.

Worked example

Initial: one rotten at (0,0), six fresh oranges, deque = [(0,0,0)].
Pop (0,0,0). Neighbours (1,0) and (0,1) are fresh. Rot both, push with t=1. fresh = 4.
Pop (1,0,1). Neighbour (1,1) is fresh. Rot, push with t=2. fresh = 3.
Pop (0,1,1). Neighbour (0,2) is fresh. Rot, push with t=2. fresh = 2.
Pop (1,1,2). Neighbour (2,1) is fresh. Rot, push with t=3. fresh = 1.
Pop (0,2,2). No fresh neighbours.
Pop (2,1,3). Neighbour (2,2) is fresh. Rot, push with t=4. fresh = 0.
Pop (2,2,4). No fresh neighbours.
BFS empty. fresh == 0. Output minutes = 4.

Notice: the answer is the max t ever popped, not the depth of the deepest pushed cell. They are equal for this problem, but tracking minutes as you pop is the more general pattern.

Complexity

Time: O(r · c). Every cell is enqueued at most once.
Space: O(r · c) for the deque and the (possibly mutated) grid.

Common pitfalls

Forgetting to count fresh oranges: without the counter you cannot distinguish "all done" from "stuck". Both empty the queue. Only the counter says "stuck = -1".
Marking rotten on pop instead of on enqueue: a fresh cell adjacent to two rotten cells gets enqueued twice, decrements fresh twice, and the second t overrides the first (often with a stale larger value). Mark '1' -> '2' at enqueue.
Returning the time of the last pop on a tray with zero rotten and zero fresh: the BFS never runs, minutes stays 0, which is the correct answer; but -1 because "the counter is zero too" is also tempting and wrong. Guard the print: -1 iff fresh > 0.
Forgetting that BFS handles the multi-source case "for free": all you do is push every source before the first pop. There is no separate algorithm.
Using a 2-D distance matrix: unnecessary. The timestamp travels with the queue tuple.

Where this shows up in the enterprise

CalFire and CAL FIRE wildfire simulators: multi-source BFS from active fire fronts, expanded by wind/fuel-modified neighbour rules, produces the next hour's predicted perimeter.
Public health contagion modelling (CDC, WHO): seed BFS with every confirmed case, expand by contact-graph adjacency, count the rounds until herd immunity.
Cloudflare attack-traffic clustering: BFS from every confirmed bot IP, expanding by traffic-similarity edges, finds the rest of the botnet in O(N+E) instead of O(N^2).
Datadog service maps: blast-radius analysis seeds the BFS with the failed services and expands along dependency edges, giving each downstream service a "minutes-to-degradation" estimate.
Twitter/X feed graph: rumour-spread experiments seed BFS with the originating users and measure the depth at which the spread peaks.
Slack channel membership: simulated mass-notification roll-out can use multi-source BFS from anchor channels to estimate the time to saturate the workspace.
Industrial defect propagation: paint defects, plating burns, or contamination spreads across a wafer in the same multi-source fashion; the rotting-oranges algorithm gives a tight lower bound on the worst-case spread time.

The shape "multiple simultaneous origins, propagation in lockstep, time to saturate" is the take-away.

Variants you'll see elsewhere

walls-and-gates: BFS from every gate, fill rooms with shortest gate distance.
01-matrix: BFS from every 0, fill each 1 with distance to its nearest 0.
as-far-from-land-as-possible: BFS from every land cell, return the maximum filled distance to a water cell.
shortest-distance-from-all-buildings: BFS from every building, sum distances cell-by-cell, return the minimum sum over empty cells. A more expensive but structurally identical extension.

All of them: seed the queue with the source set before the first pop, mark on enqueue, propagate distance in the tuple.

How parikshan turns this into a learning loop

This problem is the cluster's "multi-source BFS is one extra for loop" lesson. The recommended flow:

Practice mode for flood-fill: a single-source BFS. Internalise mark-on-enqueue.
Practice mode for rotting-oranges: replace the single source with a loop that seeds the queue from every '2' cell. The rest is identical. Notice how little the algorithm changes.
Exam mode: redo both back to back. The five-minute target on rotting-oranges should feel boring once the multi-source seeding is muscle memory.

The unreachable-case -1 is the one place where a beginner trips. parikshan's private tests include a "fresh orange behind a wall" case for exactly this reason; the integrity score will reflect whether you remembered to count fresh oranges up front.

In the AI-integrated workspace

When you direct an agent to write this, it will almost always seed BFS from the first rotten cell it sees and miss the rest. Your review must:

Confirm the seeding loop runs before the BFS loop: every '2' cell pushed with t=0, not just the first.
Confirm the fresh counter is incremented in the initial scan: only then can -1 be detected.
Confirm mark-on-enqueue: grid[nx][ny] = '2' happens at the push site, not at the pop site.
Inspect the final guard: print(-1 if fresh > 0 else minutes). The fresh > 0 ordering matters; else defaults to 0 when no spreading happened, which is the correct answer.

Senior engineers reading multi-source BFS code look at three things in order: where the queue is seeded, when cells are marked, and how the unreachable case is detected. The candidate who can articulate "all sources seeded before first pop, mark on enqueue, counter for unreachable" out loud is the candidate who ships fire-spread simulators, contagion models, and propagation analytics correctly the first time.