LeetCode 994 Rotting Oranges: Multi-Source BFS, Explained Minute by Minute

Rotting Oranges is the standard introduction to multi-source BFS, one of the most reusable ideas in grid and graph interviews. The problem itself is medium difficulty, but candidates lose points in predictable places: running a separate BFS from each rotten orange, using DFS, or getting the minute count off by one. This guide explains why a single BFS from all sources is correct, walks through a grid minute by minute, and then shows the five or six problems that are the same idea in disguise.

The Problem: How Long Until Every Orange Rots?

You get an m x n grid. Each cell is:

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

Every minute, any fresh orange that is 4-directionally adjacent (up, down, left, right) to a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if that is impossible. Constraints are small on LeetCode (1 <= m, n <= 10), but interviewers will ask about large grids, so design for O(m·n).

Why BFS, and Why DFS Gives Wrong Answers

Rot spreads one step per minute in every direction at once. So the minute at which a fresh orange rots equals its grid distance to the nearest rotten orange, measured in steps through cells that contain oranges (rot cannot travel through empty cells). The answer to the problem is the largest such distance over all fresh oranges.

Shortest distances in an unweighted graph are exactly what BFS computes. BFS dequeues cells in non-decreasing order of distance from the source, so the first time it reaches a cell, that is the shortest distance to it, and it never needs to revisit.

DFS does not have that guarantee. It might reach an orange through a long winding path first and record distance 7, when a short path of length 2 exists via a different branch. You would have to allow revisits whenever a shorter distance is found, which turns into an exponential or at best O((m·n)²) relaxation. In an interview, choosing DFS here is a strong negative signal, because "minimum steps on an unweighted grid" should trigger BFS immediately. The general rules are summarised in graph BFS and DFS interview problems.

The simulation approach, and why it is slow

A naive solution simulates minute by minute: scan the whole grid, find fresh oranges next to rotten ones, rot them (careful to use a copy so newly rotten oranges do not spread in the same minute), repeat until nothing changes. Each scan is O(m·n), and the number of minutes can be up to O(m·n) (think of a long snake-shaped path of oranges), so this is O((m·n)²). It passes LeetCode's 10 × 10 limits but is worth mentioning only as the brute force.

The Multi-Source BFS Idea

There can be several rotten oranges at the start. You could run a BFS from each of them and take, for each fresh orange, the minimum distance across all runs. With k rotten oranges that is O(k·m·n), up to O((m·n)²) again.

The better idea: put all rotten oranges in the queue at the start, each at distance 0, and run a single BFS. This works because of a simple construction:

Imagine an extra node S connected to every rotten orange. A normal BFS from S would visit S, then all rotten oranges (distance "0" after subtracting the zero-length first hop), then their neighbours, and so on. Starting the queue with all rotten oranges is just skipping the first step of that BFS. Since a single-source BFS correctly computes shortest distances from S, our queue computes, for every cell, the distance to its nearest rotten orange. Each cell enters the queue once: O(m·n) total.

Rotting Oranges Code in Python, Java and C++

Plan: one pass to enqueue every rotten orange and count fresh ones. Then BFS level by level. For each level, if anything rots, that level counts as a minute. Mark oranges rotten in the grid itself when you enqueue them, which doubles as the visited set.

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        q = deque()
        fresh = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    q.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1

        minutes = 0
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        while q and fresh > 0:
            for _ in range(len(q)):          # one full level = one minute
                r, c = q.popleft()
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2     # mark when ENQUEUING
                        fresh -= 1
                        q.append((nr, nc))
            minutes += 1

        return minutes if fresh == 0 else -1

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        int fresh = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) q.offer(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int minutes = 0;
        while (!q.isEmpty() && fresh > 0) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] cell = q.poll();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        fresh--;
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}

#include <vector>
#include <queue>
#include <utility>
using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int rows = grid.size(), cols = grid[0].size();
        queue<pair<int, int>> q;
        int fresh = 0;
        for (int r = 0; r < rows; ++r)
            for (int c = 0; c < cols; ++c) {
                if (grid[r][c] == 2) q.push({r, c});
                else if (grid[r][c] == 1) ++fresh;
            }
        const int dr[4] = {1, -1, 0, 0};
        const int dc[4] = {0, 0, 1, -1};
        int minutes = 0;
        while (!q.empty() && fresh > 0) {
            int sz = q.size();
            while (sz--) {
                int r = q.front().first, c = q.front().second;
                q.pop();
                for (int k = 0; k < 4; ++k) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        --fresh;
                        q.push({nr, nc});
                    }
                }
            }
            ++minutes;
        }
        return fresh == 0 ? minutes : -1;
    }
};

The loop condition while q and fresh > 0 is doing important work. It stops as soon as the last fresh orange rots, so we never count an extra "empty" minute where the final rotten oranges are dequeued but have nothing left to infect. It also means a grid with no fresh oranges returns 0 without entering the loop.

Complexity: each cell is enqueued at most once (we mark it rotten before enqueuing) and each dequeue checks four neighbours, so O(m·n) time. The queue can hold O(m·n) cells in the worst case. No separate visited array is needed because the grid itself records state. If the interviewer says you must not modify the input, copy the grid or keep a visited boolean matrix; complexity is unchanged.

Minute-by-Minute Dry Run

Grid from Example 1. Coordinates are (row, col). Initially the queue holds the one rotten orange (0,0), and fresh = 6.

Notice that in level 2, cell (1,1) is adjacent to both (1,0) and (0,1). It is rotted and enqueued by whichever is dequeued first, and because it is immediately marked as 2, the second neighbour skips it. Without marking at enqueue time, (1,1) would enter the queue twice. In this tiny grid that only wastes work, but in large grids duplicate enqueues can blow the queue up.

For Example 2, the BFS rots everything reachable and stops when the queue empties. The orange at (2,0) has empty cells above it and to its right, so it is never reached. fresh ends at 1, and the function returns -1.

Counting Minutes Correctly: Three Ways

The off-by-one in the minute count is the most common bug. There are three clean ways to track time, and you should pick one and stick to it.

The "time in the queue" version is often less error-prone under pressure because there is no level bookkeeping at all:

from collections import deque

def oranges_rotting_with_time(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, 0))
            elif grid[r][c] == 1:
                fresh += 1
    last = 0
    while q:
        r, c, t = 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
                last = t + 1
                q.append((nr, nc, t + 1))
    return last if fresh == 0 else -1

Because BFS assigns times in non-decreasing order, the last assignment is the maximum, so last is the answer. If nothing was fresh, last stays 0.

Edge Cases Interviewers Check

The last row is the one to dry-run aloud if you want to show you understand multi-source BFS. Starting from only the left orange would give 4; starting from both gives 2, because the middle orange is two steps from each end.

The Same Pattern: Walls and Gates, 01 Matrix and More

Multi-source BFS shows up whenever you need "distance to the nearest source" for every cell. Recognising this saves you from writing a BFS per cell (which is O((m·n)²) and a common wrong turn).

Walls and Gates (LeetCode 286)

Grid of -1 (wall), 0 (gate) and INF (empty room, 2³¹ − 1). Fill each room with the distance to its nearest gate. Seed the queue with every gate. When you pop a cell at distance d, any neighbour still at INF gets d + 1 and is enqueued. Rooms that stay INF are unreachable.

from collections import deque

def walls_and_gates(rooms):
    if not rooms:
        return
    INF = 2**31 - 1
    rows, cols = len(rooms), len(rooms[0])
    q = deque((r, c) for r in range(rows) for c in range(cols) if rooms[r][c] == 0)
    while q:
        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 rooms[nr][nc] == INF:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

It is Rotting Oranges with the distance stored in the grid instead of a level counter. The "INF means unvisited" check plays the role of "fresh".

More problems with the same skeleton

For a broader set of grid problems, including flood fill and island counting, see matrix and grid interview problems and the island-counting walkthrough in LeetCode 200 Number of Islands. When edges have different weights, BFS no longer gives shortest paths and you need Dijkstra or 0-1 BFS, covered in shortest path algorithms explained.

Multi-source BFS outside grids

The trick is not grid-specific. Topological sort with Kahn's algorithm is a multi-source BFS: you seed the queue with every node of in-degree 0. "Find the nearest hospital for every city" on a road network with unit weights is the same pattern. In production systems, the same layered spreading model describes failure cascades or rumour propagation in a social graph, which is a useful sentence if an interviewer asks for real-world relevance. See topological sort interview problems for the Kahn's algorithm version.

How Rotting Oranges Shows Up in Interviews

This problem is popular in online assessments and first-round interviews at Amazon, Microsoft and many Indian product companies because it tests graph modelling on a grid with very little setup. The interviewer is looking for three things:

1. Pattern recognition. Do you say "minimum time on an unweighted grid, so BFS" within the first minute? Do you seed all rotten oranges, rather than BFS from each?
2. Correct bookkeeping. Fresh counter, marking on enqueue, level counting without the extra minute, the -1 and 0 cases.
3. Explaining correctness. Why does one BFS from many sources give the nearest-source distance? The super-source argument is the cleanest answer.

Follow-up questions to expect

• "Return the grid of times instead of the max." Use the distance-matrix version.
• "Some oranges are immune." Treat them like empty cells (or like walls). Clarify whether immune oranges count toward the "all rotten" condition.
• "Rot takes 2 minutes to cross certain cells." Now edges have weights 1 or 2. Use Dijkstra, or split weighted edges into unit steps. 0-1 BFS applies only when weights are 0 or 1.
• "The grid is 10⁵ × 10⁵ and does not fit in memory." Discuss processing row bands, storing only the frontier, or that the honest answer is a distributed BFS (frontier-based, level synchronous). This is about reasoning, not code.
• "Can you do it without modifying the input?" Use a visited matrix or a copy.

Mistakes that cost candidates

• Running BFS separately from each rotten orange and taking minimums: correct but O(k·m·n).
• Marking cells as visited when dequeued instead of when enqueued: duplicates in the queue, and in the level-loop version, possibly double-decrementing fresh.
• Returning minutes - 1 as a hack to fix a level-counting bug, which then breaks the no-fresh-oranges case.
• Forgetting that the queue can start empty (no rotten oranges) while fresh oranges exist: the answer is -1.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.