📖 5 min read
Last updated on

Rotting Oranges — Coding Interview Walkthrough

By intervu.dev

Hero Image for Rotting Oranges

The core approach: Rotting Oranges is solved with multi-source BFS in O(m×n) time and O(m×n) space. Seed the queue with all initially rotten oranges simultaneously. Spread rot to adjacent fresh oranges level by level, each level representing one minute. After BFS, if any fresh orange remains, return -1; otherwise return the total minutes elapsed.

You’re in a coding interview. The interviewer says: “A grid has fresh and rotten oranges. Each minute, rotten oranges infect all adjacent fresh oranges. How many minutes until all oranges are rotten?” You know this is BFS — the minute-by-minute spread from multiple sources is a textbook multi-source BFS problem. The challenge is recognizing that you need to seed the queue with all rotten oranges simultaneously, not one at a time.

Already know how to solve Rotting Oranges? Try a Rotting Oranges mock interview on Intervu →

The Problem

You are given an m x n integer grid where each cell is:

  • 0 — empty
  • 1 — fresh orange
  • 2 — rotten orange

Every minute, any fresh orange adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes for all fresh oranges to rot, or -1 if it is impossible.

Example

Input: [[2,1,1],[1,1,0],[0,1,1]] Output: 4

What Interviewers Are Actually Testing

SkillWhat Interviewers Observe
Multi-source BFSDo you seed the queue with ALL rotten oranges at once?
Layer-by-layer BFSDo you track minutes via BFS levels?
Fresh count trackingDo you count fresh oranges upfront and decrement?
Impossible caseDo you detect unreachable fresh oranges and return -1?

Step 1: Clarifying Questions

  1. 4-directional or 8-directional? 4-directional — no diagonals.
  2. What if there are no fresh oranges? Return 0.
  3. What if there are no rotten oranges but there are fresh ones? Return -1.

Step 2: The Key Insight

Multi-source BFS: seed the queue with every rotten orange simultaneously. This models parallel spread correctly. Each BFS level corresponds to one minute. After BFS completes, if any fresh oranges remain, return -1.

3×3 grid at t=0: rotten orange (amber) at [0,0], fresh oranges (green) at adjacent cells, empty cells (dark).

Step 3: Algorithm

  1. Scan the grid. Add all rotten oranges to a queue. Count fresh oranges.
  2. If fresh_count == 0, return 0.
  3. BFS level by level (each level = one minute): for each rotten orange, check 4 neighbors. If fresh, mark rotten, decrement fresh count, enqueue.
  4. After BFS: if fresh_count == 0, return minutes. Otherwise -1.

Python Implementation

from collections import deque

def orangesRotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c, 0))
            elif grid[r][c] == 1:
                fresh_count += 1

    if fresh_count == 0:
        return 0

    max_minutes = 0
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while queue:
        r, c, minute = queue.popleft()
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh_count -= 1
                max_minutes = max(max_minutes, minute + 1)
                queue.append((nr, nc, minute + 1))

    return max_minutes if fresh_count == 0 else -1

Time & Space Complexity

AspectComplexity
TimeO(m × n) — each cell enqueued at most once
SpaceO(m × n) — queue can hold all cells

Common Interview Mistakes

  1. Single-source BFS. Running BFS from each rotten orange separately models sequential spread, not simultaneous. Results are wrong for grids with multiple rotten oranges.

  2. Off-by-one on minutes. Tracking minutes with a level counter can produce ±1 bugs. Storing the time in the queue entry itself is cleanest.

  3. Not checking for remaining fresh oranges. BFS completing doesn’t mean all oranges are rotten. Check fresh_count == 0.

What a Strong Candidate Sounds Like

“This is multi-source BFS. I seed the queue with all rotten oranges at once to model simultaneous spread. Each BFS level is one minute. I track fresh count upfront and decrement as oranges rot. After BFS, if any fresh remain, they’re isolated and I return -1.”

Example Interview Dialogue

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

Candidate: Because the spread is simultaneous. If two rotten oranges are on opposite ends of the grid, they infect neighbors at the same time. Multi-source BFS models this by starting all sources at minute 0. Running BFS from each source sequentially would double-count time.

Interviewer: How do you detect impossible cases?

Candidate: I count fresh oranges before BFS. Each time a fresh orange turns rotten, I decrement. After BFS, if fresh_count > 0, those oranges were never reached — I return -1.

Frequently Asked Questions

Why is Breath-First Search (BFS) superior to DFS for Rotting Oranges?

Because multiple distinct rotten oranges simultaneously spread contamination outwards by exactly one uniform step per minute, BFS correctly simulates this coordinated radial expansion level-by-level across the entire grid concurrently without prioritizing isolated deep paths.

How do you track grid infection timelines effortlessly?

You initially push all pre-existing rotten oranges into a unified queue while simultaneously tallying any healthy cells. By cyclically expanding that queue outwards in generational batches and decrementing healthy counts upon contamination, the final total minutes resolve automatically.

Practice This in a Mock Interview

Rotting Oranges is a reliable signal for BFS fluency. The multi-source seeding is the insight that separates a good answer from a correct-but-naive one. If you can explain why single-source BFS is wrong and implement multi-source confidently, you’re ready for any BFS variant.

Start a mock interview for Rotting Oranges on Intervu.

Further reading:

Practice Like It's the Real Interview

Get instant feedback on your approach, communication, and code — powered by AI.

Start a Mock Interview →