994. Rotting Oranges (Medium)

Problem

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

0, empty
1, fresh orange
2, rotten orange

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if impossible.

Example

grid = [[2,1,1],[1,1,0],[0,1,1]] → 4
grid = [[2,1,1],[0,1,1],[1,0,1]] → -1 (the bottom-left fresh orange is unreachable)
grid = [[0,2]] → 0

LeetCode 994 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, simulate minute-by-minute

Swift

final class Solution {
    func orangesRotting(_ grid: [[Int]]) -> Int {
        var grid = grid, minutes = 0
        while true {
            var toRot: [(Int, Int)] = []
            for row in grid.indices { for col in grid[0].indices where grid[row][col] == 1 {
                if [(1,0),(-1,0),(0,1),(0,-1)].contains(where: { dr, dc in
                    let nr = row + dr, nc = col + dc
                    return nr >= 0 && nr < grid.count && nc >= 0 && nc < grid[0].count && grid[nr][nc] == 2
                }) { toRot.append((row, col)) }
            } }
            if toRot.isEmpty { break }
            for (row, col) in toRot { grid[row][col] = 2 }
            minutes += 1
        }
        return grid.joined().contains(1) ? -1 : minutes
    }
}

On each tick, scan the grid and mark any fresh orange adjacent to a rotten one. Keep ticking until no more changes.

Complexity

Time: $O((m * n)$ ²), driven by up to m * n ticks, each doing an $O(m * n)$ scan.
Space: $O(m * n)$ for the to_rot list.

Correct but slow.

Approach 2: Multi-source BFS (optimal)

Seed a BFS queue with every rotten orange at time 0; process levels. When the queue empties, time = last recorded minute. Return -1 if any fresh orange remains.

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])             # L1: grid dimensions
    q = deque()
    fresh = 0
    for r in range(rows):                            # L2: seed queue + count fresh
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c, 0))                  # L3: enqueue rotten with t=0
            elif grid[r][c] == 1:
                fresh += 1                           # L4: count fresh

    time = 0
    while q:                                         # L5: BFS loop
        r, c, t = q.popleft()                        # L6: O(1) dequeue
        time = t                                     # L7: track latest minute
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2                     # L8: rot neighbor
                fresh -= 1                           # L9: decrement fresh count
                q.append((nr, nc, t + 1))            # L10: enqueue with incremented time

    return time if fresh == 0 else -1                # L11: check for unreachable

function orangesRotting(grid: number[][]): number {
    const rows = grid.length, cols = grid[0].length;  // L1: grid dimensions
    const q: [number, number, number][] = [];
    let fresh = 0;
    for (let r = 0; r < rows; r++) {                  // L2: seed queue + count fresh
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 2) q.push([r, c, 0]); // L3: enqueue rotten with t=0
            else if (grid[r][c] === 1) fresh++;       // L4: count fresh
        }
    }

    let time = 0, head = 0;
    while (head < q.length) {                         // L5: BFS loop
        const [r, c, t] = q[head++];                  // L6: O(1) dequeue
        time = t;                                     // L7: track latest minute
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
                grid[nr][nc] = 2;                     // L8: rot neighbor
                fresh--;                              // L9: decrement fresh count
                q.push([nr, nc, t + 1]);              // L10: enqueue with incremented time
            }
        }
    }

    return fresh === 0 ? time : -1;                   // L11: check for unreachable
}

final class Solution {
    func orangesRotting(_ grid: [[Int]]) -> Int {
        var grid = grid
        let rows = grid.count, cols = grid[0].count
        var queue: [(Int, Int)] = [], head = 0, fresh = 0, minutes = 0
        for row in 0..<rows { for col in 0..<cols { if grid[row][col] == 2 { queue.append((row, col)) } else if grid[row][col] == 1 { fresh += 1 } } }
        while head < queue.count && fresh > 0 {
            let levelEnd = queue.count
            while head < levelEnd {
                let (row, col) = queue[head]; head += 1
                for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
                    let nr = row + dr, nc = col + dc
                    if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
                        grid[nr][nc] = 2; fresh -= 1; queue.append((nr, nc))
                    }
                }
            }
            minutes += 1
        }
        return fresh == 0 ? minutes : -1
    }
}

Where the time goes, line by line

Variables: m = grid rows, n = grid cols.

Line	Per-call cost	Times executed	Contribution
L2 (seed scan)	$O(1)$	m * n	$O(m * n)$
L3, L4 (enqueue/count)	$O(1)$	m * n	$O(m * n)$
L6 (dequeue)	$O(1)$	once per cell	*$O(m n)$ ← dominates**
L8, L9 (rot + decrement)	$O(1)$	once per fresh cell	$O(m * n)$
L10 (enqueue)	$O(1)$	once per fresh cell	$O(m * n)$
L11 (return check)	$O(1)$	1	$O(1)$

Each cell enters the queue at most once (L8 marks it 2 before L10 enqueues it, preventing re-entry). The scan in L2 and the BFS in L5 together visit every cell a constant number of times.

Complexity

Time: $O(m * n)$ , driven by L6/L10 (each cell enqueued and dequeued at most once).
Space: $O(m * n)$ queue worst case (all cells rotten from the start).

Why multi-source BFS works

Think of all rotten oranges as simultaneous “starting points” of a BFS. The depth of any fresh orange in this BFS is its minute-to-rot. The overall answer is the max depth, which is the time the last orange rots.

Approach 3: BFS without per-cell time tuple (level batching)

Same idea, drop per-entry time tag; use level-by-level batching.

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])             # L1: grid dimensions
    q = deque()
    fresh = 0
    for r in range(rows):                            # L2: seed queue + count fresh
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))                     # L3: enqueue rotten, no time tag
            elif grid[r][c] == 1:
                fresh += 1                           # L4: count fresh

    time = 0
    while q and fresh > 0:                           # L5: BFS loop, stop early if no fresh
        time += 1                                    # L6: advance clock once per level
        for _ in range(len(q)):                      # L7: process exactly one level
            r, c = q.popleft()                       # L8: O(1) dequeue
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2                 # L9: rot neighbor
                    fresh -= 1                       # L10: decrement fresh count
                    q.append((nr, nc))               # L11: enqueue for next level

    return -1 if fresh > 0 else time                 # L12: check for unreachable

function orangesRotting(grid: number[][]): number {
    const rows = grid.length, cols = grid[0].length;  // L1: grid dimensions
    const q: [number, number][] = [];
    let fresh = 0;
    for (let r = 0; r < rows; r++) {                  // L2: seed queue + count fresh
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 2) q.push([r, c]);     // L3: enqueue rotten, no time tag
            else if (grid[r][c] === 1) fresh++;       // L4: count fresh
        }
    }

    let time = 0, head = 0;
    while (head < q.length && fresh > 0) {            // L5: BFS loop, stop early if no fresh
        time++;                                       // L6: advance clock once per level
        const levelEnd = q.length;
        while (head < levelEnd) {                     // L7: process exactly one level
            const [r, c] = q[head++];                 // L8: O(1) dequeue
            for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
                    grid[nr][nc] = 2;                 // L9: rot neighbor
                    fresh--;                          // L10: decrement fresh count
                    q.push([nr, nc]);                 // L11: enqueue for next level
                }
            }
        }
    }

    return fresh > 0 ? -1 : time;                     // L12: check for unreachable
}

final class Solution {
    func orangesRotting(_ grid: [[Int]]) -> Int {
        var grid = grid
        let rows = grid.count, cols = grid[0].count
        var queue: [(Int, Int)] = [], head = 0, fresh = 0, minutes = 0
        for row in 0..<rows { for col in 0..<cols { if grid[row][col] == 2 { queue.append((row, col)) } else if grid[row][col] == 1 { fresh += 1 } } }
        while head < queue.count && fresh > 0 {
            let levelEnd = queue.count
            while head < levelEnd {
                let (row, col) = queue[head]; head += 1
                for (dr, dc) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
                    let nr = row + dr, nc = col + dc
                    if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
                        grid[nr][nc] = 2; fresh -= 1; queue.append((nr, nc))
                    }
                }
            }
            minutes += 1
        }
        return fresh == 0 ? minutes : -1
    }
}

Complexity

Time: $O(m * n)$ , driven by L8/L11 (each cell processed once).
Space: $O(m * n)$ queue; slightly less memory per entry than Approach 2 (no t tuple element).

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Summary

Approach	Time	Space
Simulate minute-by-minute	$O((m * n)$ ^2)	$O(m * n)$
Multi-source BFS	*$O(m n)$**	*$O(m n)$**
Multi-source BFS + level batching	$O(m * n)$	$O(m * n)$

Multi-source BFS is the canonical template for “fire/water/infection spreads from multiple starts” problems. Same pattern: Walls and Gates (286), 01 Matrix (542), As Far From Land As Possible (1162).

# Quick smoke tests, paste into a REPL or save as test_994.py and run.
# Uses the canonical implementation (Approach 2: multi-source BFS).

from collections import deque

def oranges_rotting(grid):
    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, 0))
            elif grid[r][c] == 1:
                fresh += 1

    time = 0
    while q:
        r, c, t = q.popleft()
        time = t
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh -= 1
                q.append((nr, nc, t + 1))

    return time if fresh == 0 else -1

def _run_tests():
    # Example 1 from problem statement
    assert oranges_rotting([[2,1,1],[1,1,0],[0,1,1]]) == 4

    # Example 2: unreachable fresh orange
    assert oranges_rotting([[2,1,1],[0,1,1],[1,0,1]]) == -1

    # Example 3: no fresh oranges
    assert oranges_rotting([[0,2]]) == 0

    # All fresh, no rotten: impossible
    assert oranges_rotting([[1,1],[1,1]]) == -1

    # All empty
    assert oranges_rotting([[0]]) == 0

    # Single rotten, single fresh adjacent
    assert oranges_rotting([[2,1]]) == 1

    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function orangesRotting(grid: number[][]): number {
    const rows = grid.length, cols = grid[0].length;
    const q: [number, number, number][] = [];
    let fresh = 0;
    for (let r = 0; r < rows; r++)
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === 2) q.push([r, c, 0]);
            else if (grid[r][c] === 1) fresh++;
        }

    let time = 0, head = 0;
    while (head < q.length) {
        const [r, c, t] = q[head++];
        time = t;
        for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
                grid[nr][nc] = 2; fresh--; q.push([nr, nc, t + 1]);
            }
        }
    }
    return fresh === 0 ? time : -1;
}

console.assert(orangesRotting([[2,1,1],[1,1,0],[0,1,1]]) === 4);
console.assert(orangesRotting([[2,1,1],[0,1,1],[1,0,1]]) === -1);
console.assert(orangesRotting([[0,2]]) === 0);
console.assert(orangesRotting([[1,1],[1,1]]) === -1);
console.assert(orangesRotting([[0]]) === 0);
console.assert(orangesRotting([[2,1]]) === 1);
console.log("all tests pass");

Arrays, grid
Queues, BFS engine with multi-source seeding

BFS, the level order frontier pattern for shortest unweighted distance and wave expansion.
Graph Traversal, the visited set model for exploring nodes and edges without repetition.

994. Rotting Oranges (Medium)

Problem

Try it yourself

Approach 1: Brute force, simulate minute-by-minute

Approach 2: Multi-source BFS (optimal)

Why multi-source BFS works

Approach 3: BFS without per-cell time tuple (level batching)

Summary

Test cases

Related data structures

Related concepts