LeetCode 994 · Graphs

Rotting Oranges, explained with a picture

Rot spreading through a fruit crate.

MediumGraphs
▶ Watch it step by step

The problem

In a grid, 2 = rotten orange, 1 = fresh, 0 = empty. Every minute, each rotten orange rots its fresh neighbours (up, down, left, right). How many minutes until no fresh orange is left? Return −1 if that never happens.

Input:  211 / 110 / 011
Output: 4

Picture it

Picture a crate of oranges. All the rotten oranges start spreading at the same time, like ripples. We put every rotten orange in a queue together and spread one “wave” per minute. If some fresh orange is never reached (walled off by empty spaces), the answer is −1.

How to recognise it

  • Something spreads outwards from several starting points at once, one step per unit of time.
  • The question asks for the time until everything is reached, or whether that never happens.
  • All starting points begin at the same moment, so there is no single source.
  • Grids are small here (at most 10 × 10), but the pattern is the same one used for far larger floods.

Start with brute force

Simulate each minute literally. Scan the whole grid, and every fresh orange with a rotten neighbour becomes rotten in a copy of the grid. Repeat until a minute changes nothing, then check whether any fresh orange remains.

def rotting_brute(grid):
    g, minutes = [row[:] for row in grid], 0
    while True:
        new = [row[:] for row in g]
        changed = False
        for r, c in all_cells(g):
            if g[r][c] == 1 and any(g[a][b] == 2 for a, b in nbrs(g, r, c)):
                new[r][c] = 2
                changed = True
        if not changed:
            break
        g, minutes = new, minutes + 1
    return -1 if any(1 in row for row in g) else minutes

Each minute costs O(R·C) for the scan and the copy. In the worst case the rot snakes through a path that is about R·C/2 cells long, so there can be about R·C/2 minutes and the total is O((R·C)²). For a 10 × 10 crate that is trivial, but for 1000 × 1000 it is roughly 5 × 10^11 steps. Space is O(R·C).

From brute force to the idea

  1. Find the waste. Most of each scan looks at cells that cannot possibly change this minute: only oranges next to freshly rotten ones matter.
  2. Keep a frontier. The queue holds the oranges that rotted most recently. Start it with every rotten orange, and count the fresh ones.
  3. Process one minute at a time. for _ in range(len(q)) takes exactly the oranges that are in the queue right now, which is one level of the search. Their fresh neighbours rot, are queued for the next level, and fresh drops by one each time.
  4. Count levels. After a level is done, minutes += 1. The loop stops as soon as the queue is empty or fresh reaches 0, so no extra minute is added after the last orange rots.
  5. Decide the answer. If fresh is 0 return minutes, otherwise some orange was walled off and the answer is -1.

The key idea: this is BFS started from all rotten oranges together, and each BFS level is one minute.

The key idea

Multi-source BFS: all starting points enter the queue at once, and each level is one minute. O(rows × cols).

Python solution

def oranges_rotting(grid):
    q, fresh = deque(), 0
    for r, c in all_cells(grid):
        if grid[r][c] == 2: q.append((r, c))
        if grid[r][c] == 1: fresh += 1
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):
            r, c = q.popleft()
            for nr, nc in nbrs(grid, r, c):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

def all_cells(g):
    return [(r, c) for r in range(len(g))
            for c in range(len(g[0]))]

def nbrs(g, r, c):  # in-grid neighbours
    R, C = len(g), len(g[0])
    for nr, nc in ((r+1, c), (r-1, c),
                   (r, c+1), (r, c-1)):
        if 0 <= nr < R and 0 <= nc < C:
            yield nr, nc

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO((R·C)²): up to about R·C/2 minutes, each scanning the gridO(R·C): a copy of the grid each minute
Multi-source BFS (shown code)O(R·C): each orange is queued at most once, with four neighbour checksO(R·C): the queue and the list from all_cells; the grid is changed in place

Edge cases

  • No fresh oranges ([[0]], [[2]], [[0,2]]): returns 0, even when there is no rotten orange.
  • Fresh oranges but nothing rotten ([[1]]): returns -1.
  • A fresh orange cut off by empty cells ([[2,0,1]]): returns -1.
  • Already all rotten ([[2]]): returns 0.
  • Diagonals do not spread rot, so [[2,1,1],[0,1,1],[1,0,1]] returns -1 because the bottom-left orange is isolated.
  • The grid is modified, and deque must be imported.

Common mistakes

  • Starting a separate BFS from each rotten orange, which gives wrong times and wastes work.
  • Counting minutes per orange popped instead of per level.
  • Looping while q only, which counts one extra minute after the last orange rots.
  • Forgetting to check fresh at the end, so unreachable oranges return a time instead of -1.
  • Marking an orange rotten only when it is popped, so it can be queued twice.
Your turn: rot after m minutes

Return how many fresh oranges have rotted after exactly m minutes. Describe what changes, then write it if you like.

Compare with our answer

The level-by-level loop is the same, but it runs for exactly m levels (or until the queue empties) and counts the oranges it rots.

def rotted_after(grid, m):
    q, rotted = deque(), 0
    for r, c in all_cells(grid):
        if grid[r][c] == 2:
            q.append((r, c))
    for _ in range(m):
        for _ in range(len(q)):
            r, c = q.popleft()
            for nr, nc in nbrs(grid, r, c):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    rotted += 1
                    q.append((nr, nc))
    return rotted

Time O(R·C), space O(R·C). If the queue empties early the later minutes do nothing.

A strong answer mentions: multi-source BFS, a bounded number of levels instead of a fresh counter, and why levels correspond to minutes.

Check what stuck

1. A grid has 0s and 1s. You must write, in every cell, its distance (in steps up, down, left or right) to the nearest 1. Which approach fits best?

2. Why does the shown code loop for _ in range(len(q)) inside the while?

3. A learner changes the last line to return minutes. Which input now returns a wrong answer?

Score 60% or more and the lesson is marked complete.