Rotting Oranges

35 min · orangesRotting()

One spoiled orange can ruin a crate, but only if the rot can physically reach the rest. The clock makes that reach measurable.

You're given a rectangular grid whose cells mean:

0: empty space,
1: a fresh orange, and
2: a rotten orange.

During each minute, every rotten orange spreads rot to any fresh orange directly above, below, left, or right of it. All spreading within a minute happens at the same time.

Return the number of minutes needed to leave no fresh orange behind. Return -1 when at least one fresh orange can never be reached. If the grid starts with no fresh oranges, return 0.

Constraints

1 <= grid.length <= 100
1 <= grid[i].length <= 100
Every row has the same length.
Every cell is 0, 1, or 2.

Hints

Start with the clock

You can copy the grid, scan every cell, mark the fresh neighbors of rotten cells, and repeat until a scan changes nothing. What work gets repeated each minute?

Many starting points, one wave

Every orange that is rotten at minute 0 belongs in the same initial queue. Process that whole layer before increasing the minute count.

Count what remains

Track the number of fresh oranges. Each orange enters the queue only when it first rots, and the final count tells you whether an isolated pocket survived.

Follow-up

How would you return a second grid containing the exact minute when each reachable orange rots, while keeping the same time complexity?

Visible cases

Examples

Example 1

ready

Input: grid = [ [ 2, 1, 1 ], [ 1, 1, 0 ], [ 0, 1, 1 ] ]
Expected: 4
Why: the rot reaches the final orange after four synchronized waves

Example 2

ready

Input: grid = [ [ 2, 1, 1 ], [ 0, 1, 1 ], [ 1, 0, 1 ] ]
Expected: -1
Why: the fresh orange in the lower-left corner is cut off by empty cells

Example 3

ready

Input: grid = [ [ 0, 2 ] ]
Expected: 0
Why: there are no fresh oranges at the start

Interview signal

Asked at

AmazonGoogleMicrosoft

Minute-by-minute simulation

The direct model treats the grid like a sequence of snapshots. During one full scan, collect every fresh orange touched by today's rotten oranges. Change those cells only after the scan, so an orange that rots now can't spread again during the same minute.

def oranges_rotting(grid: list[list[int]]) -> int:
    cells = [row[:] for row in grid]
    rows, cols = len(cells), len(cells[0])
    minutes = 0
 
    while True:
        newly_rotten: list[tuple[int, int]] = []
        for row in range(rows):
            for col in range(cols):
                if cells[row][col] != 1:
                    continue
                for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < rows and 0 <= nc < cols and cells[nr][nc] == 2:
                        newly_rotten.append((row, col))
                        break
 
        if not newly_rotten:
            break
        for row, col in newly_rotten:
            cells[row][col] = 2
        minutes += 1
 
    has_fresh = any(1 in row for row in cells)
    return -1 if has_fresh else minutes

Time O((mn)²) in the worst case — up to mn minutes, with a full mn scan each time. Space O(mn) for the current minute's changed cells.

Multi-source BFS — spread one shared wave

Multi-source breadth-first search (BFS) starts the same shortest-path search from several sources at once. Here, every initially rotten orange is a source. A queue layer is exactly one minute, so the BFS structure already contains the clock we need.

Count fresh oranges first. Seed the queue with every rotten position, then process one whole queue layer at a time. When a fresh neighbor rots, decrement the count and enqueue it once. Empty cells never enter the search.

from collections import deque
 
 
def oranges_rotting(grid: list[list[int]]) -> int:
    cells = [row[:] for row in grid]
    rows, cols = len(cells), len(cells[0])
    queue: deque[tuple[int, int]] = deque()
    fresh = 0
 
    for row in range(rows):
        for col in range(cols):
            if cells[row][col] == 2:
                queue.append((row, col))
            elif cells[row][col] == 1:
                fresh += 1
 
    minutes = 0
    while queue and fresh:
        for _ in range(len(queue)):
            row, col = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = row + dr, col + dc
                if 0 <= nr < rows and 0 <= nc < cols and cells[nr][nc] == 1:
                    cells[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
 
    return minutes if fresh == 0 else -1

Mark a cell rotten when you enqueue it, not when you later remove it. That prevents two parents in the same layer from adding the same orange twice.

Time O(mn) — each cell is inspected a constant number of times. Space O(mn) for the queue in the widest wave.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraygrid: int[][]

Expected

Run: visible + custom · Submit: full suite