What is the brute force approach and complexity for Rotting Oranges?

Each minute, scan the whole grid and rot the fresh oranges that touch a rotten one with time complexity O((R · C)²) and space complexity O(R · C).

What is the optimal approach and complexity for Rotting Oranges?

Put every rotten orange in the queue at once; each BFS level is one minute with optimal time complexity O(R · C) and space complexity O(R · C).

How do you identify the pattern for Rotting Oranges?

Look for key signals in the prompt: "every rotten orange, all at once" indicates Several starting points spread at the same time, so all of them go into the queue first.; "each minute, the four neighbours" indicates One step on the grid is one minute, so one BFS level is one minute.; "minimum number of minutes" indicates Each orange rots at its shortest distance from the nearest rotten orange, which is what BFS measures.; "return -1 if some orange never rots" indicates If the queue runs dry while fresh oranges are left, those oranges were never reached..

Rotting Oranges

Medium·LeetCode #994Basic Anchor

LeetCode

Jump:

30-Second Mental ModelMulti-source BFS (level by level)

Complexity:O((R · C)²)→O(R · C)

Key Insight

Put all the rotten oranges in a queue at minute 0. Pop one level at a time. Each level is one minute: every fresh neighbour of a popped orange rots and joins the queue for the next minute. Stop when no fresh orange is left. If the queue empties first, return -1.

Core Validity Invariant

At the start of a level, the queue holds exactly the oranges that rotted in the previous minute, so popping that many cells processes one whole minute and nothing from the next one.

Problem

You get a grid. Each cell is an empty cell, a fresh orange, or a rotten orange. Every minute, each fresh orange that touches a rotten orange on one of its four sides (up, down, left or right) rots as well.

Return the number of minutes until no fresh orange is left. If some fresh orange can never be reached by the rot, return -1.

Input

grid, an m × n grid. 0 = empty cell, 1 = fresh orange, 2 = rotten orange.

Output

The number of minutes until no fresh orange is left, or -1 if one of them never rots.

Example 1

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]

Output: 4

Minute 1 rots the two oranges next to the top-left one. Minute 2 rots (0,2) and (1,1). Minute 3 rots (2,1), and minute 4 rots the last one, (2,2).

Example 2

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]

Output: -1

The orange at (2,0) has only empty cells next to it, so no rot can ever reach it.

Example 3

Input: grid = [[0,2]]

Output: 0

There is no fresh orange at the start, so no minute is needed.

Constraints

• The grid has m rows and n columns, with 1 ≤ m, n ≤ 10.
• Each cell is 0, 1 or 2.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If only one rotten orange starts the rot, how many minutes does it need to reach a fresh orange? What does that number measure?
2.
What if two rotten oranges sit far apart? Does a fresh orange wait for the rot from just one of them?
3.
How could I simulate the grid minute by minute? What would I have to look at in each minute?
4.
Which oranges rot in minute 2? Can I find them without scanning the whole grid again?
5.
How would I know the rot can never finish? What would still be on the grid at the end?

Brute force approach

Idea

Each minute, scan every cell. A fresh orange rots if it touches a rotten orange from before this minute. Collect those cells during the scan and rot them after the scan, then count the minute. Stop when a minute rots nothing. If a fresh orange is still left, return -1.

Thinking process

1
The rule is simple: a fresh orange rots when a rotten one touches it. So I can copy that rule into a loop and run it minute by minute.
2
Check on [[2,1,1],[1,1,0],[0,1,1]]. Minute 1: (0,1) and (1,0) touch (0,0), so they rot. The cell (1,1) touches (0,1) and (1,0), but neither was rotten before minute 1, so (1,1) must wait.
3
Minute 2 now rots (1,1), because (0,1) and (1,0) were rotten before minute 2. If I rotted cells during the scan, (0,2) would touch the new rotten (0,1) and rot in minute 1, which is wrong. So the rotting waits until the scan is done.
4
Minutes 1 to 4 each rot something, and minute 5 rots nothing. So the answer is 4.

Visual

Green = rotten before this minute, purple = rots in this minute. Each minute scans all R · C cells, even when only a few change.

Brute force: sweep the whole grid every minutegrid = [[2,1,1,0],[1,1,0,2],[0,1,1,1]]step 1/5

grid

Sweep

minute: 0
fresh left: 7

Minute 0: the rotten oranges as given

Brute force does not use a queue. It keeps the grid and asks each minute: which fresh oranges touch a rotten one? Green = rotten before this minute.

Code & Implementation

brute.cpp

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        const int dr[] = {-1, 1, 0, 0};
        const int dc[] = {0, 0, -1, 1};
        int minutes = 0;
        while (true) {
            // One full sweep. Collect the cells first, so a cell that rots this minute
            // cannot spread the rot to its neighbour in the same minute.
            vector<pair<int, int>> toRot;
            for (int r = 0; r < m; r++)
                for (int c = 0; c < n; c++) {
                    if (grid[r][c] != 1) continue;
                    for (int d = 0; d < 4; d++) {
                        int nr = r + dr[d], nc = c + dc[d];
                        if (nr >= 0 && nc >= 0 && nr < m && nc < n && grid[nr][nc] == 2) {
                            toRot.push_back({r, c});
                            break;
                        }
                    }
                }
            if (toRot.empty()) break;      // nothing changed in this minute: we are done
            for (auto [r, c] : toRot) grid[r][c] = 2;
            minutes++;
        }
        for (auto& row : grid)
            for (int v : row)
                if (v == 1) return -1;     // a fresh orange was never reached
        return minutes;
    }
};

import java.util.*;

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        int minutes = 0;
        while (true) {
            // One full sweep. Collect the cells first, so a cell that rots this minute
            // cannot spread the rot to its neighbour in the same minute.
            List<int[]> toRot = new ArrayList<>();
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (grid[r][c] != 1) continue;
                    for (int d = 0; d < 4; d++) {
                        int nr = r + dr[d], nc = c + dc[d];
                        if (nr >= 0 && nc >= 0 && nr < m && nc < n && grid[nr][nc] == 2) {
                            toRot.add(new int[]{r, c});
                            break;
                        }
                    }
                }
            }
            if (toRot.isEmpty()) break;      // nothing changed in this minute: we are done
            for (int[] cell : toRot) grid[cell[0]][cell[1]] = 2;
            minutes++;
        }
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) return -1;     // a fresh orange was never reached
            }
        }
        return minutes;
    }
}

from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dr = [-1, 1, 0, 0]
        dc = [0, 0, -1, 1]
        minutes = 0
        while True:
            # One full sweep. Collect the cells first, so a cell that rots this minute
            # cannot spread the rot to its neighbour in the same minute.
            to_rot = []
            for r in range(m):
                for c in range(n):
                    if grid[r][c] != 1:
                        continue
                    for d in range(4):
                        nr, nc = r + dr[d], c + dc[d]
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 2:
                            to_rot.append((r, c))
                            break
            if not to_rot:
                break      # nothing changed in this minute: we are done
            for r, c in to_rot:
                grid[r][c] = 2
            minutes += 1

        for r in range(m):
            for c in range(n):
                if grid[r][c] == 1:
                    return -1     # a fresh orange was never reached
        return minutes

export function orangesRotting(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    let minutes = 0;
    while (true) {
        // One full sweep. Collect the cells first, so a cell that rots this minute
        // cannot spread the rot to its neighbour in the same minute.
        const toRot: [number, number][] = [];
        for (let r = 0; r < m; r++) {
            for (let c = 0; c < n; c++) {
                if (grid[r][c] !== 1) continue;
                for (let d = 0; d < 4; d++) {
                    const nr = r + dr[d];
                    const nc = c + dc[d];
                    if (nr >= 0 && nc >= 0 && nr < m && nc < n && grid[nr][nc] === 2) {
                        toRot.push([r, c]);
                        break;
                    }
                }
            }
        }
        if (toRot.length === 0) break;      // nothing changed in this minute: we are done
        for (const [r, c] of toRot) grid[r][c] = 2;
        minutes++;
    }
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 1) return -1;     // a fresh orange was never reached
        }
    }
    return minutes;
}

Complexity

Time O((R · C)²)Space O(R · C)

Each minute scans all R · C cells. The rot can take up to R · C minutes, for example a long line of fresh oranges that rots one cell per minute. The space is the list of cells that rot in one minute, which can hold up to R · C cells.

Optimized approach

Idea

Start from brute force

Brute force scans the whole grid every minute and asks which fresh oranges touch a rotten one. The queue already holds exactly the oranges that can change this minute, so the scan is not needed.

Find the repeated work

Each minute scans all R · C cells, but only the oranges on the edge of the rot can change. Cells in the middle of the rot, or cells that touch only empty cells, are scanned again in every later minute for nothing.

Define the state — what variables do I need?

queue: Rotten oranges that have not spread to their neighbours yet. One BFS level is the group of oranges that rotted in the same minute.
minutes: How many levels have been processed. Each level is one minute.
fresh: How many cells still hold a fresh orange. It starts at the number of 1s and goes down by one each time an orange rots.

Define validity

At the start of a level, the queue holds exactly the oranges that rotted in the previous minute, so popping that many cells processes one whole minute and nothing from the next one.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

Push every 2 into the queue; count the 1s into fresh.

All rotten oranges start at minute 0, so they form one shared front.

Start of each level

minutes++, then level = queue.size()

This level is one minute. Its oranges are exactly the queue at this moment, because the new ones are only pushed while this level is popped.

Each of the level pops

For each of the four neighbours that is 1: set it to 2, decrease fresh, and push it.

The neighbour rots during this minute, so it spreads only in the next minute. Pushing it to the back puts it in the next level.

The loop test

while (fresh > 0 && !queue.empty())

Stop as soon as no fresh orange is left, or when the queue runs dry with fresh oranges still left, which means -1.

What does the current window add to the answer?

Each level that rots at least one orange adds one minute. When fresh reaches 0, the last minute counted is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        queue<pair<int, int>> q;
        int fresh = 0;
        // Every rotten orange starts in the queue together, at minute 0.
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 2) q.push({r, c});
                else if (grid[r][c] == 1) fresh++;
            }

        const int dr[] = {-1, 1, 0, 0};
        const int dc[] = {0, 0, -1, 1};
        int minutes = 0;
        while (fresh > 0 && !q.empty()) {
            minutes++;                 // one BFS level = one minute
            int level = q.size();      // exactly the oranges that rotted in the previous minute
            for (int k = 0; k < level; k++) {
                auto [r, c] = q.front();
                q.pop();
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] != 1) continue;
                    grid[nr][nc] = 2;  // rots during this minute; it spreads in the next one
                    fresh--;
                    q.push({nr, nc});
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
};

import java.util.*;

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> q = new ArrayDeque<>();
        int fresh = 0;
        // Every rotten orange starts in the queue together, at minute 0.
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 2) q.offer(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        int minutes = 0;
        while (fresh > 0 && !q.isEmpty()) {
            minutes++;                 // one BFS level = one minute
            int level = q.size();      // exactly the oranges that rotted in the previous minute
            for (int k = 0; k < level; k++) {
                int[] cell = q.poll();
                int r = cell[0], c = cell[1];
                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d], nc = c + dc[d];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] != 1) continue;
                    grid[nr][nc] = 2;  // rots during this minute; it spreads in the next one
                    fresh--;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
}

from typing import List
from collections import deque

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        q = deque()
        fresh = 0
        # Every rotten orange starts in the queue together, at minute 0.
        for r in range(m):
            for c in range(n):
                if grid[r][c] == 2:
                    q.append((r, c))
                elif grid[r][c] == 1:
                    fresh += 1

        dr = [-1, 1, 0, 0]
        dc = [0, 0, -1, 1]
        minutes = 0
        while fresh > 0 and q:
            minutes += 1                 # one BFS level = one minute
            level = len(q)              # exactly the oranges that rotted in the previous minute
            for _ in range(level):
                r, c = q.popleft()
                for d in range(4):
                    nr, nc = r + dr[d], c + dc[d]
                    if nr < 0 or nc < 0 or nr >= m or nc >= n or grid[nr][nc] != 1:
                        continue
                    grid[nr][nc] = 2    # rots during this minute; it spreads in the next one
                    fresh -= 1
                    q.append((nr, nc))

        return minutes if fresh == 0 else -1

export function orangesRotting(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const q: [number, number][] = [];
    let fresh = 0;
    // Every rotten orange starts in the queue together, at minute 0.
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            if (grid[r][c] === 2) q.push([r, c]);
            else if (grid[r][c] === 1) fresh++;
        }
    }

    const dr = [-1, 1, 0, 0];
    const dc = [0, 0, -1, 1];
    let minutes = 0;
    let head = 0;
    while (fresh > 0 && head < q.length) {
        minutes++;                 // one BFS level = one minute
        const level = q.length - head;      // exactly the oranges that rotted in the previous minute
        for (let k = 0; k < level; k++) {
            const [r, c] = q[head++];
            for (let d = 0; d < 4; d++) {
                const nr = r + dr[d];
                const nc = c + dc[d];
                if (nr < 0 || nc < 0 || nr >= m || nc >= n || grid[nr][nc] !== 1) continue;
                grid[nr][nc] = 2;  // rots during this minute; it spreads in the next one
                fresh--;
                q.push([nr, nc]);
            }
        }
    }
    return fresh === 0 ? minutes : -1;
}

Complexity

Time O(R · C)Space O(R · C)

Each cell enters the queue at most once and is popped once, so the work is O(R · C). The queue can hold up to R · C cells in the worst case.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Each minute, scan the whole grid and rot the fresh oranges that touch a rotten one	O((R · C)²)	O(R · C)
Optimal	Put every rotten orange in the queue at once; each BFS level is one minute	O(R · C)	O(R · C)

Why does this belong to this pattern?

Clues in the problem statement

“every rotten orange, all at once”Several starting points spread at the same time, so all of them go into the queue first.
“each minute, the four neighbours”One step on the grid is one minute, so one BFS level is one minute.
“minimum number of minutes”Each orange rots at its shortest distance from the nearest rotten orange, which is what BFS measures.
“return -1 if some orange never rots”If the queue runs dry while fresh oranges are left, those oranges were never reached.

Grid cells as nodes+many sources at distance 0+one BFS level = one minute+answer = the last level that rots something→Multi-source BFS (level by level)

This is the anchor of Multi-source BFS. Start one BFS with every rotten orange already in the queue, because the rot spreads from all of them together. The answer is the number of levels, which is the time for the rot to reach the last orange from its nearest rotten neighbour. A flood-fill question asks only which cells are connected; this question also counts the levels.

Don't make this mistake

Pattern confusion: a BFS from each rotten orange, then combining the answers

✗ for (auto [r, c] : rotten) answer = max(answer, bfsTimeFrom(r, c));

✓ queue = all rotten oranges at minute 0; one BFS over the whole grid

On the dry-run grid [[2,1,1,0],[1,1,0,2],[0,1,1,1]], a BFS from (0,0) alone needs 5 minutes and a BFS from (1,3) alone needs 6. Taking the maximum gives 6, but the real answer is 3. Each orange is reached by whichever rotten orange is nearest, and the two sources spread together.

Rotting during the scan

✗ for each cell: if it is fresh and touches a rotten cell, set it to 2 right away

✓ collect the cells first, then rot them after the scan (brute force)

On [[2,1,1],[1,1,0],[0,1,1]], scanning row by row rots (0,1) first, so (0,2) then touches a rotten cell and rots in minute 1. The whole grid rots in one sweep and the answer comes out as 1 instead of 4.

Forgetting the -1 case

✗ return minutes;

✓ return fresh == 0 ? minutes : -1;

On [[2,1,1],[0,1,1],[1,0,1]] the queue empties after 4 minutes, but the orange at (2,0) is still fresh. Returning minutes gives 4 instead of -1.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Graph BFS / DFS translate into production architectures and low-level memory mechanics.

LLD Real-World Story

Food Delivery System (Zomato / DoorDash)

Geospatial indexing and shortest dispatch routing for delivery partners.

Explore Track

C++ Internals

Virtual Method Table (vtable) & Dynamic Dispatch

Polymorphic graph nodes and state machine execution overhead.

Explore Track

01 Matrix