DSA Rotten Oranges

The problem

Rotten Oranges gives a grid of cells. Each cell is empty, holds a fresh orange, or holds a rotten orange.

The numbers mark the states. Zero means empty, one means fresh, and two means rotten.

Every minute, each rotten orange rots its fresh side neighbours. Side neighbours share an edge, never just a corner. The answer is the minutes until no fresh orange remains, or minus one when some fresh orange can never rot.

cases = [
    ([[2, 1, 1], [1, 1, 0], [0, 1, 1]], 4),
    ([[2, 1], [1, 1]], 2),
    ([[1, 2], [1, 1], [0, 0], [1, 1]], -1),
    ([[0, 2]], 0),
]
for grid, expected in cases:
    print("grid", grid, "-> minutes:", expected)

The third grid strands fresh oranges below a row of empty cells. No rot crosses that row, so its answer is minus one. The last grid holds no fresh orange at all, so it needs zero minutes.

Intuition: follow one rotten orange

The first idea follows a single rotten orange. Its rot spreads one ring at a time. The minutes for that orange are the distances to the cells it rots.

The trap is the second rotten orange. Two sources spread at the same time in the real process. Following only one source credits it with cells the other source rots sooner.

from collections import deque

grid = [[2, 1, 1, 1, 2]]
rows, cols = 1, 5
dist = [[-1] * cols for _ in range(rows)]
queue = deque([(0, 0)])
dist[0][0] = 0
while queue:
    r, c = queue.popleft()
    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and dist[nr][nc] == -1:
            dist[nr][nc] = dist[r][c] + 1
            queue.append((nr, nc))
print("minutes from the left orange alone:", max(max(row) for row in dist))

The left orange alone needs three minutes for the fourth cell. The right orange rots that cell in one minute. The true answer for this row is two minutes, and only a search that starts from both oranges at once finds it.

Brute force: rescan the whole grid every minute

The brute force copies the grid once per minute. In each copy, every rotten cell rots its fresh neighbours. The copies stop the rot from running ahead inside a single minute.

A scan that changes nothing while fresh oranges remain proves the task impossible. A fresh count of zero ends the loop with the minute count.

def minutes_brute(grid):
    grid = [row[:] for row in grid]
    rows, cols = len(grid), len(grid[0])
    checks = 0
    minutes = 0
    while True:
        fresh = 0
        for row in grid:
            fresh += row.count(1)
        if fresh == 0:
            return minutes, checks
        changed = False
        nxt = [row[:] for row in grid]
        for r in range(rows):
            for c in range(cols):
                checks += 1
                if grid[r][c] == 2:
                    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < rows and 0 <= nc < cols and nxt[nr][nc] == 1:
                            nxt[nr][nc] = 2
                            changed = True
        grid = nxt
        if not changed:
            return -1, checks
        minutes += 1

for grid in ([[2, 1, 1], [1, 1, 0], [0, 1, 1]], [[1, 2], [1, 1], [0, 0], [1, 1]]):
    minutes, checks = minutes_brute(grid)
    print("minutes:", minutes, "cell checks:", checks)

The method is correct and wasteful. Every minute rechecks every cell, including cells that rotted long ago. The check count is the minute count times the cell count.

The optimal solution: start one wave from every rotten orange

Multi-source BFS is a breadth-first search whose queue starts with every rotten cell at once, so each level of the queue is exactly one minute of spread. That one sentence is the whole method.

Breadth-first search visits cells level by level from its starting cells. A fresh count tracks the oranges still waiting. The search stops when the count reaches zero.

from collections import deque

def minutes_to_rot(grid):
    if not grid or not grid[0]:
        return 0
    grid = [row[:] for row in grid]
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    if fresh > 0:
        return -1
    return minutes

cases = [
    ([[2, 1, 1], [1, 1, 0], [0, 1, 1]], 4),
    ([[2, 1], [1, 1]], 2),
    ([[1, 2], [1, 1], [0, 0], [1, 1]], -1),
    ([[0, 2]], 0),
]
for grid, expected in cases:
    result = minutes_to_rot(grid)
    print("grid", grid, "->", result, "expected:", expected, "match:", result == expected)

All four cases pass. Each cell enters the queue at most once, because a rotted cell is marked two and never matches the fresh test again.

Walkthrough: four minutes on the first grid

The queue starts with the single rotten cell at the top left. Each level below is one minute of spread. The fresh count drops as the wave moves.

from collections import deque

grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
queue = deque()
fresh = 0
for r in range(3):
    for c in range(3):
        if grid[r][c] == 2:
            queue.append((r, c))
        elif grid[r][c] == 1:
            fresh += 1
print("minute 0 fresh:", fresh)
for row in grid:
    print(row)
minutes = 0
while queue and fresh > 0:
    for _ in range(len(queue)):
        r, c = queue.popleft()
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < 3 and 0 <= nc < 3 and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                queue.append((nr, nc))
    minutes += 1
    print("minute", minutes, "fresh:", fresh)
    for row in grid:
        print(row)

The last fresh orange sits at the bottom right. The wave reaches it at minute four. The answer is read off the minute counter when the fresh count hits zero.

Complexity

The brute force rescans all cells on every minute, so its time grows with the minutes times the cells. The wave search visits each cell once, so its time is O(rows times cols).

Both methods store one grid copy at most, so their extra space is O(rows times cols) for the copy. The queue also holds at most one entry per cell.

from collections import deque

def brute_checks(n):
    grid = [[1] * n for _ in range(n)]
    grid[0][0] = 2
    checks = 0
    while any(1 in row for row in grid):
        nxt = [row[:] for row in grid]
        for r in range(n):
            for c in range(n):
                checks += 1
                if grid[r][c] == 2:
                    for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < n and 0 <= nc < n and nxt[nr][nc] == 1:
                            nxt[nr][nc] = 2
        grid = nxt
    return checks

def bfs_visits(n):
    grid = [[1] * n for _ in range(n)]
    grid[0][0] = 2
    queue = deque([(0, 0)])
    visits = 0
    while queue:
        r, c = queue.popleft()
        visits += 1
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                queue.append((nr, nc))
    return visits

for n in (2, 3, 4):
    print("size", n, "- brute checks:", brute_checks(n), " bfs visits:", bfs_visits(n))

At size 4 the brute force pays 96 checks against 16 visits. The gap grows with both the grid and the minute count. Counting checks shows the gap without any clock.

Edge cases and pitfalls

An empty grid has nothing to rot. The answer is zero, and the code must not read a first row that does not exist.

A grid with fresh oranges but no rotten orange can never start. Its answer is minus one, not zero.

from collections import deque

def minutes_to_rot(grid):
    if not grid or not grid[0]:
        return 0
    grid = [row[:] for row in grid]
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    if fresh > 0:
        return -1
    return minutes

print("empty grid:", minutes_to_rot([]))
print("no fresh oranges:", minutes_to_rot([[0, 2]]))
print("no rotten orange:", minutes_to_rot([[1, 1]]))
print("fresh boxed in by an empty cell:", minutes_to_rot([[2, 0, 1]]))
print("all empty:", minutes_to_rot([[0, 0]]))

The boxed-in row shows the quieter trap. A rotten orange sits two cells away, but an empty cell blocks the path. Reachability decides this problem, never distance alone.