Rotting Oranges

Table of Contents +

Rotting Oranges is the question that teaches you multi source BFS. The rot spreads from many oranges at once, not one. So you cannot start from a single point. Once you see how to start from all rotten oranges together, this problem becomes easy.

🎯 The Problem

You get a grid of oranges. Each cell is one of three things:

  • 0 is an empty cell.
  • 1 is a fresh orange.
  • 2 is a rotten orange.

The rules:

  • Every minute, each rotten orange rots its fresh neighbors. Up, down, left, right only.
  • All rotten oranges spread at the same moment, every minute.
  • Return the number of minutes until no fresh orange is left.
  • If a fresh orange can never be reached, return -1.

Here is a small grid.

Input grid (0 empty, 1 fresh, 2 rotten):
  2  1  1
  1  1  0
  0  1  1


Minute by minute the rot spreads:
  start -> the 2 rots its neighbors
  ... until every fresh orange turns rotten


Output: 4

The answer counts the minutes until the last fresh orange rots. Each minute, every currently rotten orange spreads to its fresh neighbors at the same time.

Here is the start. One rotten orange sits at the top left. It will spread to its fresh neighbors.

minute 1

minute 1

minute 2

minute 2

rotten 0,0

fresh 0,1

fresh 1,0

fresh 0,2

fresh 1,1

🐢 Approach 1: Repeated Grid Scans (Brute Force)

The idea:

  • Scan the whole grid once per minute.
  • On each scan, rot the fresh neighbors of every rotten cell.
  • Stop when a full scan changes nothing.

Why it is weak:

  • You rescan the entire grid every minute, even cells that never change.
  • Many minutes means many full scans of everything.
  • Time is about O(cells × minutes). Too slow on a big grid.

Here is the repeated-scan code:

rotting_oranges_repeated_scan.py
def oranges_rotting(grid):
    minutes = 0
    while True:
        rot = []
        for r in range(len(grid)):
            for c in range(len(grid[0])):
                if grid[r][c] == 2:
                    for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
                        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 1:
                            rot.append((nr, nc))
        if not rot: break
        for r, c in rot: grid[r][c] = 2
        minutes += 1
    return -1 if any(1 in row for row in grid) else minutes

⚡ Approach 2: Multi-Source BFS (Best)

The idea in one line: start from every rotten orange at once, then spread outward in rings, one ring per minute.

What BFS gives us:

  • BFS (breadth first search) explores in layers using a queue.
  • A queue is a line: you add to the back and take from the front.
  • “Multi source” means we load every rotten orange into the queue before we start.

How one minute works:

  • Read the queue size first. That is the count of oranges rotten right now.
  • Process exactly that many. Rot each one’s fresh neighbors and add them to the back.
  • Those new cells belong to the next minute.
  • After the layer is cleared, add one to the minute count.

How it finishes:

  • Keep going while the queue has oranges and fresh ones remain.
  • At the end, if the fresh count is 0, return the minutes.
  • If any fresh orange is left, it was cut off. Return -1.

Why it is fast:

  • Each cell enters and leaves the queue once.
  • Time is O(cells). We touch only cells that actually change.

Here is the multi-source BFS code:

rotting_oranges_bfs.py
from collections import deque
def oranges_rotting(grid):
    q = deque()
    fresh = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == 2: q.append((r, c, 0))
            if grid[r][c] == 1: fresh += 1
    minutes = 0
    while q:
        r, c, minutes = q.popleft()
        for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 1:
                grid[nr][nc] = 2; fresh -= 1; q.append((nr, nc, minutes + 1))
    return minutes if fresh == 0 else -1

🧭 Approach 3: DFS With Timestamps (Alternative)

  • Start a DFS from each rotten orange, carrying the current minute.
  • Stamp every fresh orange with the earliest minute it could rot.
  • The answer is the largest stamp. Any unstamped fresh orange means -1.
  • It works, but overlapping paths revisit the same cells. So it is usually slower and trickier than BFS. Good to mention, but reach for BFS.

Here is the BFS spreading layer by layer. Each ring is one minute.

queue starts with all rotten

minute 1 layer rots neighbors

minute 2 layer rots their neighbors

keep going until queue empty

fresh left? yes -> -1, no -> minutes

Steps to Solve

  1. Put every rotten orange into a queue. Count every fresh orange.
  2. If there are no fresh oranges, the answer is 0 minutes.
  3. While the queue is not empty and fresh oranges remain, process one full minute.
  4. For a minute, take the current queue size. Process exactly that many oranges. For each, rot its fresh neighbors, drop the fresh count, and add the new rotten cells to the queue.
  5. After each full layer, add one to the minute count.
  6. At the end, if the fresh count is zero, return the minutes. Otherwise return -1.

This Python version uses a deque from the collections module and processes one minute at a time.

rotting_oranges.py
from collections import deque


grid = [
    [2, 1, 1],
    [1, 1, 0],
    [0, 1, 1],
]
R, C = len(grid), len(grid[0])


queue = deque()      # holds positions of rotten oranges
fresh = 0
for i in range(R):
    for j in range(C):
        if grid[i][j] == 2:
            queue.append((i, j))   # a rotten orange to spread from
        elif grid[i][j] == 1:
            fresh += 1             # count fresh oranges


minutes = 0
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]


while queue and fresh > 0:
    layer = len(queue)            # oranges rotten at the start of this minute
    for _ in range(layer):
        r, c = queue.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1:
                grid[nr][nc] = 2          # this fresh orange rots
                fresh -= 1
                queue.append((nr, nc))    # it spreads next minute
    minutes += 1


print(minutes if fresh == 0 else -1)

The output of the above code will be:

4

Now let us walk through the Python version line by line. We start by building the queue. The first double loop scans every cell. If a cell is 2, it is already rotten, so we add its position to the queue with queue.append((i, j)). If a cell is 1, it is fresh, so we add one to fresh. This is the multi source part. Every rotten orange goes in at the same time.

The check while queue and fresh > 0 keeps the loop running while there are rotten oranges to spread from and fresh oranges still left. If no fresh oranges remain we stop early. No need to keep going.

The line layer = len(queue) is the trick that handles a full minute at once. We freeze the current queue size. That number is exactly the oranges rotten at the start of this minute. The inner for _ in range(layer) then processes only those. Any new rotten oranges we add land at the back and belong to the next minute, not this one.

Inside, r, c = queue.popleft() takes one rotten orange from the front. The neighbor check 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 1 keeps us in the grid and only acts on a fresh orange. When we find one, grid[nr][nc] = 2 rots it, fresh -= 1 drops the fresh count, and queue.append((nr, nc)) lines it up to spread next minute.

After the inner loop clears one full layer, minutes += 1 counts that minute. At the end, print(minutes if fresh == 0 else -1) gives the answer. If every fresh orange rotted, we return the minutes. If any fresh orange is still left, it could not be reached, so we return -1.

⏱️ Time and Space Complexity

We add each cell to the queue at most once and process it once. So the time is O(n), where n is the number of cells. The queue can hold many cells at once, so the space is O(n) as well.

Approach Time Complexity Space Complexity
Repeated grid scan (brute force) O(n²) O(1)
Multi source BFS O(n) O(n)

Tip

When something spreads from many starting points at the same speed, reach for multi source BFS. Put every source in the queue at the start, then process the queue one layer at a time. Each layer is one step of time.

🧩 Key Takeaways

  • ✅ The rot starts from many oranges at once, so this is a multi source BFS.
  • ✅ Put every rotten orange in the queue before the spread begins.
  • ✅ Freeze the queue size at the start of each minute to process one full layer.
  • ✅ Each BFS layer equals one minute of spreading.
  • ✅ If a fresh orange remains at the end, it was cut off, so return -1.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    Why is this a multi source BFS instead of a single source one?

    Why: All rotten oranges spread at once, so every rotten orange is a starting source placed in the queue together.

  2. 2

    How do we process exactly one minute of spreading at a time?

    Why: The queue size at the start of a minute is the count of currently rotten oranges, so we process exactly that many as one layer.

  3. 3

    What do we return if a fresh orange can never be reached?

    Why: If any fresh orange is still left after the BFS finishes, it was cut off, so the answer is -1.

  4. 4

    What is the time complexity of the multi source BFS solution?

    Why: Each cell enters the queue at most once and is processed once, so the work is O(n).

Score: 0 / 4

🚀 What’s Next?

Previous Surrounded Regions Next Walls and Gates