Rotting Oranges

MediumBFS · Multi-Source Level Order🧩 Graph BFS LeetCode #994 ↗Updated Oct 30, 2026

Problem

A grid holds 0 (empty), 1 (fresh orange) or 2 (rotten orange). Every minute, each rotten orange spoils the fresh oranges directly above, below, left and right of it. Return the number of minutes until no fresh orange is left, or -1 if some fresh orange can never be reached.

Input[[2,1,1],[1,1,0],[0,1,1]]Output4

Input[[2,1,1],[0,1,1],[1,0,1]]Output-1

Input[[0,2]]Output0

1 ≤ m, n ≤ 10 · grid[i][j] ∈ {0, 1, 2}

Try it yourself

Java

class Solution {
    public int orangesRotting(int[][] grid) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

All initially rotten oranges spread simultaneously, so put them all in the queue at once (multi-source BFS). Each BFS level is exactly one minute.

PatternGraph BFS

Instinct Minimum moves, fewest steps or shortest transformation where every step costs the same: spread outward level by level with a queue.

Memory hack Ripples in a pond: every ring is one step farther, so the first ring that touches the target is the answer.

Open the Graph BFS guide →

Approaches

Brute ForceMinute-by-Minute Grid Simulation

Time O((m·n)²)Space O(m·n)

Simulate literally: each round, scan the whole grid and collect every fresh orange touching a rotten one; rot them all after the scan (so the spread is one step per minute). Stop when a round changes nothing, then check for leftovers.

Java

public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length, minutes = 0;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (true) {
        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 : dirs) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 2) {
                        toRot.add(new int[]{r, c});
                        break;
                    }
                }
            }
        }
        if (toRot.isEmpty()) break;
        for (int[] p : toRot) grid[p[0]][p[1]] = 2; // apply after the scan
        minutes++;
    }
    for (int[] row : grid)
        for (int v : row) if (v == 1) return -1;
    return minutes;
}

Obviously correct, but rescans the full grid up to m·n times.

OptimalMulti-Source BFS (Level = Minute)

Time O(m·n)Space O(m·n)

Enqueue every rotten orange and count the fresh ones. Process the queue level by level: each level rots its fresh neighbours (decrementing fresh) and costs one minute. Every cell enters the queue at most once. If fresh > 0 at the end, some orange was unreachable.

Java

public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length, fresh = 0, minutes = 0;
    Queue<int[]> queue = new LinkedList<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (grid[r][c] == 2) queue.offer(new int[]{r, c});
            else if (grid[r][c] == 1) fresh++;
        }
    }
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    while (!queue.isEmpty() && fresh > 0) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            int[] cur = queue.poll();
            for (int[] d : dirs) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2; // mark on enqueue
                    fresh--;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

Linear time; BFS order guarantees each orange rots at its earliest minute.

Pro tip

Loop on fresh > 0 too — otherwise you count an extra “empty” minute after the last orange rots.

At a glance

Level	Approach	Time	Space
Brute Force	Minute-by-Minute Grid Simulation	`O((m·n)²)`	`O(m·n)`
Optimal	Multi-Source BFS (Level = Minute)	`O(m·n)`	`O(m·n)`

Common pitfalls

Rotting oranges during the scan in the simulation — one minute spreads many steps.
Running one BFS per rotten orange instead of seeding all of them at once.
Returning 0 vs -1: no fresh oranges at all ⇒ 0.

Interview tips

Say “multi-source BFS” early — it signals you see the simultaneous spread.
Explain why BFS (not DFS): levels give the minimum time to reach each cell.
Mention you mutate the grid as the visited set; offer a copy if mutation is disallowed.

Pattern

Multi-source BFS → several starting points spread at the same speed and you need the time/distance to cover everything.

My notes saved in this browser