Rotting Oranges: why multi-source BFS beats simulating minute by minute

There is a class of grid problems where the spreading happens simultaneously from multiple sources, and time is what you are measuring. Rotting Oranges is the canonical example. The moment you see "every adjacent fresh orange turns rotten at the same minute," you are looking at multi-source BFS wearing a very thin disguise.

The problem (LeetCode 994): given an m x n grid where 0 is empty, 1 is a fresh orange, and 2 is a rotten orange — every minute, any fresh orange 4-directionally adjacent to a rotten one becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if that is impossible.

What the grid size tells you

1 <= m, n <= 10. The largest possible grid is 10×10 = 100 cells. This is tiny. It means even the naive O((m×n)²) simulation will pass comfortably — the time limit is not what separates the approaches here. What separates them is conceptual clarity and what the code teaches you about BFS in general.

That said, the bounds also tell you something else: every approach runs in milliseconds on a 10×10 grid, so when you benchmark nothing interesting happens. The reason to learn BFS here is that it composes cleanly onto the 300×300 grids in LeetCode 542 and 1162, where the simulation dies.

grid[i][j] is exactly 0, 1, or 2. No other values, no need to sanitize. This lets us mutate the grid in place — flipping a fresh orange to 2 as we infect it, so we never revisit it. No separate visited set, no extra O(m×n) space beyond the queue.

4-directional adjacency, not 8. Diagonals do not spread. This is worth stating explicitly because it is the kind of constraint that, if you misread it, produces a wrong answer that still passes most of the examples.

Simulation: the honest brute force

The straightforward reading of the problem description is to simulate it literally: each minute, scan the entire grid, mark any fresh orange adjacent to a rotten one as newly rotten, and repeat until nothing changes.

The tricky part here is that you cannot update in place during the scan — if you flip a fresh orange to rotten halfway through minute one, it will infect its neighbor during the same scan, which is wrong. Everything at the same minute should spread simultaneously. So the simulation copies the grid at the start of each minute, reads from the copy (or the original), and writes to the new version.

class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        minutes = 0
 
        while True:
            new_grid = [row[:] for row in grid]
            changed = False
 
            for i in range(rows):
                for j in range(cols):
                    if grid[i][j] == 1:
                        for di, dj in directions:
                            ni, nj = i + di, j + dj
                            if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 2:
                                new_grid[i][j] = 2
                                changed = True
                                break
 
            if not changed:
                break
 
            grid = new_grid
            minutes += 1
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:
                    return -1
 
        return minutes

public class Solution {
    public int OrangesRotting(int[][] grid) {
        int rows = grid.Length, cols = grid[0].Length;
        int[,] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int minutes = 0;
 
        while (true) {
            int[][] newGrid = new int[rows][];
            for (int i = 0; i < rows; i++) {
                newGrid[i] = new int[cols];
                Array.Copy(grid[i], newGrid[i], cols);
            }
 
            bool changed = false;
 
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    if (grid[i][j] == 1) {
                        for (int d = 0; d < 4; d++) {
                            int ni = i + directions[d, 0];
                            int nj = j + directions[d, 1];
                            if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == 2) {
                                newGrid[i][j] = 2;
                                changed = true;
                                break;
                            }
                        }
                    }
                }
            }
 
            if (!changed) break;
 
            grid = newGrid;
            minutes++;
        }
 
        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] == 1) return -1;
 
        return minutes;
    }
}

Complexity: Each minute costs O(m×n) to scan. In the worst case, the infection spreads one cell per minute across the entire grid — so up to m×n minutes, giving O((m×n)²) time. Space is O(m×n) for the copied grid.

On a 10×10 grid that means at most 10,000 operations. Practically nothing. But on a 1,000×1,000 grid (hypothetically), the simulation would hit 10^12 operations. That is where it collapses.

BFS: one pass, done

The insight that makes BFS better: the simultaneous spread is exactly what BFS models natively. A BFS processes cells level by level — one full level per minute. Start with every rotten orange already in the queue (that is the "multi-source" part), then let BFS run. Level 1 infects all fresh neighbors of the initial rotten oranges. Level 2 infects their neighbors. And so on.

No repeated scanning. No grid copies. Each cell enters the queue at most once.

from collections import deque
 
class Solution:
    def orangesRotting(self, grid: list[list[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        queue = deque()
        fresh_count = 0
 
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    fresh_count += 1
 
        if fresh_count == 0:
            return 0
 
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        minutes = 0
 
        while queue and fresh_count > 0:
            minutes += 1
            for _ in range(len(queue)):
                row, col = queue.popleft()
                for dr, dc in directions:
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                        grid[nr][nc] = 2
                        fresh_count -= 1
                        queue.append((nr, nc))
 
        return minutes if fresh_count == 0 else -1

using System.Collections.Generic;
 
public class Solution {
    public int OrangesRotting(int[][] grid) {
        int rows = grid.Length, cols = grid[0].Length;
        var queue = new Queue<(int, int)>();
        int freshCount = 0;
 
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) queue.Enqueue((i, j));
                else if (grid[i][j] == 1) freshCount++;
            }
        }
 
        if (freshCount == 0) return 0;
 
        int[,] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int minutes = 0;
 
        while (queue.Count > 0 && freshCount > 0) {
            minutes++;
            int levelSize = queue.Count;
            for (int i = 0; i < levelSize; i++) {
                var (row, col) = queue.Dequeue();
                for (int d = 0; d < 4; d++) {
                    int nr = row + directions[d, 0];
                    int nc = col + directions[d, 1];
                    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        freshCount--;
                        queue.Enqueue((nr, nc));
                    }
                }
            }
        }
 
        return freshCount == 0 ? minutes : -1;
    }
}

Complexity: The initial scan is O(m×n). The BFS itself visits each cell at most once — once a fresh orange joins the queue, it is immediately marked rotten and never queued again. Total: O(m×n) time, O(m×n) space for the queue in the worst case (all cells rotten at once).

Walking through Example 1 by hand

Grid: [[2,1,1],[1,1,0],[0,1,1]]

Initial setup: one rotten orange at (0,0). Six fresh oranges everywhere else.

Minute 1 processes level {(0,0)}. It infects (0,1) to the right and (1,0) below. Queue now holds {(0,1), (1,0)}. Fresh count drops to 4.

Minute 2 processes {(0,1), (1,0)}. (0,1) infects (0,2). (1,0) infects (1,1). Queue: {(0,2), (1,1)}. Fresh count: 2.

Minute 3 processes {(0,2), (1,1)}. (0,2) has no fresh neighbors (right is out of bounds, below is (1,2) which is 0). (1,1) infects (2,1). Queue: {(2,1)}. Fresh count: 1.

Minute 4 processes {(2,1)}. It infects (2,2). Queue empty. Fresh count: 0. Return 4.

Notice that (1,2) is 0 — an empty cell, not a fresh orange. It is never touched. The BFS naturally skips it because we only enqueue cells where grid[nr][nc] == 1.

The cases that break naive implementations

No fresh oranges at all. [[0,2]] — fresh count is zero after the initial scan. We return 0 immediately, before touching the queue. This is the most common edge case to forget if you only check "is the queue empty" at the end.

Fresh oranges with no rotten oranges. [[1,1],[1,1]] — fresh count is 4, queue is empty. The BFS while loop never runs. After the loop, fresh count is still 4, so we return -1. The code handles it without a special case.

Isolated fresh oranges. [[2,1,1],[0,1,1],[1,0,1]] — the orange at (2,0) is surrounded by empty cells on all reachable sides. BFS drains completely without ever reaching it. Fresh count is 1 at the end, so we return -1. The key is that we track fresh_count separately rather than relying on the queue — when the queue empties, we check whether anything was missed.

Single cell grids. [[2]] hits the fresh_count == 0 guard and returns 0. [[1]] has fresh count 1 and an empty queue — BFS never runs, and we return -1. [[0]] returns 0 because there are no fresh oranges to worry about.

All cells rotten. Returns 0 immediately via the fresh_count == 0 guard.

Simulation vs BFS — which one to ship

On this specific problem with its 10×10 constraint, I would still ship the BFS version. Not because the simulation fails — it does not — but because the BFS is actually shorter once you internalize the level-by-level pattern. The simulation loop is more lines and allocates a full grid copy every minute. The BFS is a single traversal.

There is a version of the BFS I have seen that skips the len(queue) trick and just increments minutes at the end of the BFS loop. That breaks. You get minutes off by one or count an empty-level minute. The level size snapshot at the start of each BFS iteration — for _ in range(len(queue)) in Python or int levelSize = queue.Count in C# — is load-bearing. It is what makes the BFS process one full minute's worth of oranges at a time.

The multi-source BFS pattern

The mental model here is: "I have multiple starting points and I want the minimum time for a wave to reach every reachable cell." That is multi-source BFS. You seed the queue with all sources at once. Each level of BFS is one time step. The depth at which a cell is first reached is its minimum distance from any source.

This pattern solves a specific family of problems:

• 542. 01 Matrix: find the shortest distance from each cell to the nearest 0. Same structure — seed the queue with every 0, BFS outward. Instead of counting oranges, you record the distance when each cell is first reached.
• 286. Walls and Gates: fill each empty room with the distance to the nearest gate. Seed with all gates, BFS outward.
• 1162. As Far from Land as Possible: find the cell farthest from any land cell. Seed with all land cells, BFS until the last water cell is reached — the minute counter at that point is the answer.
• 1091. Shortest Path in Binary Matrix: single source this time, but same BFS-on-grid mechanics. The twist is 8-directional movement and a binary obstacle.

In each case, the key question is: what goes into the queue at the start? The sources. What does each BFS level represent? One unit of time, or one unit of distance. What signals completion? Either the queue empties or you reach a specific target.

Rotting Oranges adds one wrinkle the simpler problems do not have: you need to know if BFS could not reach every fresh orange. That is why fresh_count exists. It is your measure of "did the wave cover everything reachable?" If BFS finishes and fresh_count > 0, some oranges are surrounded by empty cells and will never rot.

The series continues with course schedule, where the graph is explicit (adjacency list, not a grid) and the question is not distance but reachability — specifically, whether a cycle exists. The underlying BFS logic is the same; what changes is the representation.