Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Rotting Oranges

Rotting Oranges explained: multi-source BFS from every rotten orange at once, one level per minute. Tested Python code, pitfalls and a live grid visual.

Also searched as: rotting oranges multi-source BFS · minimum minutes until all oranges rot

🏝️

Try it live Free

Number of Islands & Grid BFS

In the Grid BFS lab, watch BFS expand from S in distance rings; Rotting Oranges is the same flood started from every rotten orange at once.

Also useful: Graph Search: BFS vs DFS

Open the playground →

The problem

In a grid, 0 is empty, 1 is a fresh orange and 2 is a rotten orange. Every minute, each rotten orange rots its fresh neighbours (up, down, left, right). Return the minimum minutes until no fresh orange is left, or -1 if some can never rot.

Inputgrid = [[2,1,1],[1,1,0],[0,1,1]]
Output4
Inputgrid = [[2,1,1],[0,1,1],[1,0,1]]
Output-1

The bottom-left orange is cut off.

The key insight

Rot spreads in rings, exactly like BFS layers. The key move is multi-source BFS: put every rotten orange in the queue at time 0, then process the queue one level per minute. Count fresh oranges up front; if any remain when the queue empties, the answer is -1.

Brute force first: Simulating minute by minute with a full grid scan each minute works but costs O((m·n)²) in the worst case.

Step-by-step approach

  1. Scan the grid: push every rotten orange onto a queue and count the fresh ones.
  2. If there are no fresh oranges, return 0.
  3. Process the queue level by level; each level is one minute.
  4. For each rotten cell popped, rot every fresh neighbour, decrement the fresh count, and push it.
  5. After the BFS, return the minutes elapsed if fresh is 0, else -1.

Python solution

PYTHON 3tested
from collections import deque


def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    q, fresh = deque(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))       # every rotten orange is a BFS source
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while q and fresh:
        for _ in range(len(q)):        # one level = one minute
            r, c = q.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

Complexity

TimeO(m·n)
SpaceO(m·n)

Each orange is enqueued at most once when it rots, and each pop checks 4 neighbours. The queue can hold O(m·n) cells.

Common mistakes

Frequently asked questions

What is the time and space complexity of Rotting Oranges?

O(m·n) time because each cell is enqueued and processed at most once, and O(m·n) space for the queue in the worst case.

Why multi-source BFS instead of BFS from each rotten orange?

All rotten oranges spread at the same time. Seeding the queue with all of them makes BFS layers equal to minutes, so the first time a fresh orange is reached is its true rotting time.

What if there are no fresh oranges at the start?

The answer is 0, even if there are no rotten oranges either. Check the fresh count before the BFS.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.