Skip to content

115 — Rotting Oranges

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

115 — Rotting Oranges

LeetCode 994 · Medium. In a grid, each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, a rotten orange rots any adjacent fresh orange. Return the minimum number of minutes until no cell has a fresh orange, or -1 if that's impossible.

🍽️ Intuition

"Minutes until every orange rots" is a giveaway for level-by-level BFS: each "minute" is exactly one layer of the search, since every fresh orange adjacent to any currently-rotten orange rots simultaneously, all at once, at the same minute. The wrinkle that makes this different from single-source BFS is that rot can start from many oranges at the same time — so the BFS needs every initially-rotten orange in the queue before minute 1 even begins, not just one.

🚩 Pattern-Recognition Cue

"Something spreads to all its neighbors simultaneously, every time step, from multiple starting points at once" is the cue for multi-source, level-by-level BFS: seed the queue with every source at once, and count levels (not individual cells) to get the number of time steps.

🐢 Brute Force

Simulate minute by minute, but rescan the entire grid from scratch each minute to find which fresh oranges are currently adjacent to a rotten one, repeating until a full pass produces no change.

func orangesRottingBruteForce(_ grid: [[Int]]) -> Int {
    var grid = grid
    let rows = grid.count
    guard rows > 0 else { return 0 }
    let cols = grid[0].count
    let dirs = [(1,0),(-1,0),(0,1),(0,-1)]

    func hasFresh() -> Bool {
        for r in 0..<rows {
            for c in 0..<cols where grid[r][c] == 1 { return true }
        }
        return false
    }

    var minutes = 0
    while hasFresh() {
        var toRot: [(Int, Int)] = []
        for r in 0..<rows {
            for c in 0..<cols {
                guard grid[r][c] == 1 else { continue }
                for (dr, dc) in dirs {
                    let nr = r + dr, nc = c + dc
                    if nr >= 0, nr < rows, nc >= 0, nc < cols, grid[nr][nc] == 2 {
                        toRot.append((r, c))
                        break
                    }
                }
            }
        }
        if toRot.isEmpty { return -1 }   // fresh oranges remain but nothing new can rot
        for (r, c) in toRot { grid[r][c] = 2 }
        minutes += 1
    }
    return minutes
}

Big-O: O((m·n)²) worst case — up to O(m·n) minutes can pass (rot spreading one row at a time), each requiring a full O(m·n) grid rescan.

🚀 Optimal

Multi-source BFS: seed the queue with every initially-rotten orange at once, then process the queue level by level, where each level corresponds to exactly one minute.

func orangesRotting(_ grid: [[Int]]) -> Int {
    var grid = grid
    let rows = grid.count
    guard rows > 0 else { return 0 }
    let cols = grid[0].count
    let dirs = [(1,0),(-1,0),(0,1),(0,-1)]

    var queue: [(Int, Int)] = []
    var fresh = 0
    for r in 0..<rows {
        for c in 0..<cols {
            if grid[r][c] == 2 { queue.append((r, c)) }
            else if grid[r][c] == 1 { fresh += 1 }
        }
    }

    if fresh == 0 { return 0 }

    var minutes = 0
    var head = 0
    while head < queue.count {
        let levelSize = queue.count - head
        var rottedThisLevel = false
        for _ in 0..<levelSize {
            let (r, c) = queue[head]
            head += 1
            for (dr, dc) in dirs {
                let nr = r + dr, nc = c + dc
                guard nr >= 0, nr < rows, nc >= 0, nc < cols, grid[nr][nc] == 1 else { continue }
                grid[nr][nc] = 2
                fresh -= 1
                queue.append((nr, nc))
                rottedThisLevel = true
            }
        }
        if rottedThisLevel { minutes += 1 }
    }

    return fresh == 0 ? minutes : -1
}

// smoke test
print(orangesRotting([[2,1,1],[1,1,0],[0,1,1]]))   // 4
print(orangesRotting([[2,1,1],[0,1,1],[1,0,1]]))   // -1

Big-O: O(m·n) time — every cell enters the queue at most once, and each edge (cell-to-neighbor check) is examined once. O(m·n) space for the queue.

🔑 The Key Insight

The brute force treats "a minute passes" as an excuse to re-derive the entire rot frontier from the full grid every single time — most of that rescan revisits cells that rotted minutes ago and can never change again. The optimal version instead tracks only the active frontier — the queue holds exactly the oranges that just rotted, and only their neighbors get examined next. That's the same level-by-level discipline as any multi-source BFS: instead of asking the whole grid "what changed?" every round, only look at what changed last round, since that's the only thing that could possibly cause new changes this round.

🔗 Related Chapters

  • Queues and Deques — the index-based head pointer avoids O(n) removeFirst() calls, the same queue-as-array trick used throughout this wiki's BFS implementations.
  • BFS — multi-source, level-by-level BFS is precisely this pattern: seed multiple starts, process one full level per "step," and the number of levels processed is the answer.
  • Matrix Traversal — the four-directional bounds-checked neighbor walk is identical to every other grid problem in this chapter.

🧸 Memory Sentence

Rotting Oranges is multi-source BFS wearing a stopwatch — seed the queue with every rotten orange at once, and count levels, because a level is a minute.

✅ Check Your Understanding

  1. Why does levelSize need to be captured as queue.count - head before the inner loop starts, rather than just looping while head < queue.count without a level boundary?
  2. rottedThisLevel guards whether minutes gets incremented. Construct a grid where, without that guard, orangesRotting would return one more than the correct answer.
  3. If the grid started with fresh oranges completely surrounded by empty cells (no rotten oranges anywhere), what does the function return, and which line guarantees that?

⬅️ Previous: Surrounded Regions · Next: Walls and Gates ➡️

Clone this wiki locally