Rotting Oranges

Difficulty: Medium

Problem

You are given an m × n grid describing a crate of fruit. Each cell is 0 (empty), 1 (a fresh orange), or 2 (a rotten orange). During every minute, each rotten orange spoils all fresh oranges directly above, below, left, or right of it, and all of these changes happen at the same moment. Return how many minutes it takes until there is no fresh orange left. If some fresh orange can never be reached, return -1.

Example

Input: grid = [[1,1,0],[1,1,1],[0,1,2]]
Output: 4
Explanation: The rot starts at the bottom-right corner. Minute 1 spoils (1,2) and (2,1); minute 2 reaches (1,1); minute 3 reaches (0,1) and (1,0); minute 4 reaches the last fresh orange at (0,0).

Brute-force approach

There is no slower-but-sensible alternative here, simulating the rot minute by minute IS the problem, and multi-source BFS is that simulation in its natural form. DFS can't even model simultaneous spreading.

Optimal approach

Key insight: Seed the queue with EVERY rotten orange. Each BFS wave is exactly one minute of rot. The clock and the algorithm are the same thing.

Seed the queue with every rotten orange, count the fresh ones, then let BFS spread the rot one full wave per minute. When the simulation stops, the fresh counter delivers the verdict: 0 means return minutes, anything else means -1.

Steps

  1. Scan the grid once: enqueue every rotten cell, count every fresh cell
  2. While the queue has cells AND fresh oranges remain, process one full wave, snapshot len(queue) first
  3. Each popped cell infects its 4-directional fresh neighbors: mark rotten immediately, fresh -= 1, enqueue
  4. After each full wave, minutes += 1, one wave is one minute
  5. Return minutes if fresh == 0, otherwise -1, someone was walled off

Time complexity: O(rows × cols) · Space complexity: O(rows × cols) queue

Pseudocode

function orangesRotting(grid):
    queue = new Queue containing ____          // seed: who is rotten at t = 0?
    fresh = count of cells equal to 1
    minutes = 0

    while queue is not empty and fresh > 0:
        waveSize = ____                         // freeze this minute's wave
        repeat waveSize times:
            (r, c) = queue.pop()
            for each in-bounds neighbor (nr, nc) of (r, c):
                if grid[nr][nc] == 1:
                    ____                        // infect on discovery!
                    fresh -= 1
                    queue.push((nr, nc))
        minutes += 1

    return minutes if ____ else -1

Hints

  • Seed: rot already sits on every 2 in the grid, and all of it spreads at the same instant. How many cells should enter the queue before the first wave?
  • The snapshot: freeze the queue's size RIGHT NOW. Exactly that many cells form this minute's wave; anything enqueued mid-wave belongs to the next minute.
  • Infect on discovery: what value stamps a cell as rotten? Write it the moment you find the fresh neighbor, so two rotten neighbors can't both claim the same orange.
  • The verdict: the rot has spread as far as it ever can. What must the fresh counter read for the answer to be minutes rather than -1?

Complexity questions

What is the time complexity for an m × n grid?

O(m × n): the census scans every cell once, and each orange enters and leaves the queue at most once. Marking oranges rotten on discovery means no cell is ever enqueued twice, so the BFS does at most m × n pops with four constant-time neighbor checks each. Add the single setup scan and the total stays O(m × n).

What is the worst-case size of the queue?

O(m × n): picture a grid that is ALL rotten at t = 0: every single cell sits in the queue before the first wave. Multi-source seeding makes the worst case easy to picture: a grid of nothing but 2s puts all m × n cells into the queue immediately, before a single pop. So the queue is O(m × n): the same order as the grid itself.

Why do we set grid[nr][nc] = 2 the moment we DISCOVER a fresh orange, instead of when we later pop it from the queue?

Two rotten neighbors would otherwise BOTH enqueue the same fresh orange. It gets double-rotted, fresh is decremented twice, and the counts (and verdict) go wrong. In our example, (1,1) borders both (0,1) and (1,0), which pop in the same wave. Marked on discovery, the first stamps it rotten and the second skips it. Marked on pop instead, BOTH would enqueue it: fresh drops by 2 for one orange, the queue bloats with duplicates, and the final fresh == 0 check can lie.

The grid contains fresh oranges but ZERO rotten ones. What does the algorithm return?

-1: the queue starts empty, no rot ever spreads, fresh stays positive, and the final check fails. With no sources, no wave ever launches: [[1]] returns -1 because that orange can never rot. Contrast that with grids holding NO fresh oranges ([[2]] or [[0,2]]) where fresh starts at 0, the loop body never runs, and minutes = 0 is correctly returned. One return line handles all of it.

Check your understanding of Rotting Oranges

Rot spreads from every rotten orange to all its fresh neighbors at the same time. Why is BFS the right traversal here, and not DFS?

BFS, rot spreads in WAVES: everything at distance d from the rot rots at minute d, and BFS's level-by-level order IS the passage of time. DFS would race down one long corridor, 'rotting' the fifth orange in a chain before the rot has even touched an orange sitting right next to a source. That is not how simultaneous spreading works. BFS processes cells strictly by distance from the nearest rot, and distance from the rot is exactly the minute an orange rots.

This is your first MULTI-SOURCE BFS. At time 0, what goes into the queue?

ALL the rotten oranges, together: the rot expands from every source at once. Rot is already sitting on every 2 in the grid, and every one of them starts spreading at the same instant. So one scan drops them ALL into the queue before the first wave. That's the entire meaning of 'multi-source': the BFS itself doesn't change at all.

The rot spreads once per minute. In the code, what marks the boundary of one minute?

One full wave: snapshot len(queue), process exactly that many cells, THEN minutes += 1. It's the level-size snapshot from tree level order, wearing a lab coat. Everything currently in the queue spreads rot during THIS minute; anything enqueued along the way belongs to the NEXT minute. Freeze the size, drain exactly that many, then tick the clock.

When must the function return -1?

When some fresh orange is unreachable, walled off by empty cells, so it survives even after the queue drains. Rot cannot cross empty cells. A fresh orange fenced in by 0s (and the grid's edge) will never be touched by any wave, no matter how long we simulate. That's why we count the fresh oranges at the start: after the queue drains, check 'any fresh left?'. Fresh > 0 means someone survived, so return -1.

Trace grid = [[2,1,1],[1,1,0],[0,1,1]]. The rot starts at the top-left corner. Which orange rots LAST?

The bottom-right orange at (2,2), at minute 4. The wave must snake around the empty cells. The 0s at (1,2) and (2,0) block the direct routes, so the wave has to snake. Minute 1 rots (0,1) and (1,0); minute 2 rots (0,2) and (1,1); minute 3 rots (2,1); and only at minute 4 does the rot finally turn the corner into (2,2).

Keep practising