Skip to content
DSA Grind
All 26 sections

Rotting Oranges (LC 994)

ProblemMediumLeetCode 994Updated
On this page

Pattern: Queue — Multi-Source BFS
Difficulty: Medium
Key Concept: Everything rots simultaneously, so seed the queue with all rotten cells before the loop starts. BFS levels then equal elapsed minutes.

Problem Statement

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

  • 0 — empty
  • 1 — a fresh orange
  • 2 — 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’s impossible.

Input: int[][] grid, 1 <= m, n <= 10
Output: int — minutes, or -1

Example

[[2,1,1],          minute 0        minute 1        minute 2        minute 3        minute 4
 [1,1,0],          2 1 1           2 2 1           2 2 2           2 2 2           2 2 2
 [0,1,1]]          1 1 0    →      2 1 0    →      2 2 0    →      2 2 0    →      2 2 0
                   0 1 1           0 1 1           0 1 1           0 2 1           0 2 2

Output: 4

1. Algorithm & Pseudocode

Wrong instinct: run BFS from each rotten orange separately

for each rotten cell: BFS the whole grid, record distances, take min per fresh cell

Correct but O(R · m · n) — and it misses the point: the sources spread at the same time.

Optimal (multi-source BFS)

queue = empty
fresh = 0

// PASS 1 — seed the queue with EVERY rotten cell, and count the fresh ones
for each cell (r,c):
    if grid[r][c] == 2: queue.offer((r,c))
    if grid[r][c] == 1: fresh++

if fresh == 0: return 0                  // nothing to rot — answer is 0, not -1

minutes = 0
while queue not empty AND fresh > 0:
    size = queue.size()                  // ← FREEZE: this is one full minute
    for i in 1..size:
        (r,c) = queue.poll()
        for each of the 4 neighbours (nr,nc):
            if in bounds AND grid[nr][nc] == 1:
                grid[nr][nc] = 2         // mark rotten WHEN ENQUEUED, not when polled
                fresh--
                queue.offer((nr,nc))
    minutes++

return fresh == 0 ? minutes : -1         // leftover fresh = unreachable

2. Step-by-Step Analysis (Beginner-Friendly)

  1. Recognising it as BFS at all “Minimum number of minutes” over an unweighted grid = shortest path = BFS. Each minute is exactly one BFS level. DFS would give you a path, not the shortest one.

  2. Why multi-source, and why it’s free All rotten oranges spread in parallel. Instead of running BFS R times and taking minimums, put all R sources in the queue at level 0. BFS then naturally expands the closest source to each cell first — you get the min-over-sources for free, in a single O(m·n) pass. This is the single most reusable queue trick in interviews.

  3. int size = q.size() is what makes levels work Freezing the queue size before the inner loop means you process exactly the cells that rotted in the previous minute, and the ones you enqueue belong to the next minute. Drop this line and the levels smear together and your minute count is wrong.

  4. Mark rotten on ENQUEUE, never on dequeue If you only set grid[nr][nc] = 2 when you poll it, the same cell can be enqueued by several neighbours in the same minute. You’d double-count fresh, blow up the queue, and still be counting the same orange twice. Mark at enqueue time — this is the general BFS rule (“mark visited when you add, not when you remove”).

  5. The fresh counter answers both questions It tells you when to stop early, and at the end fresh > 0 means those oranges were walled off by empty cells and can never rot → return -1. You don’t need a second grid sweep.

  6. The fresh == 0 early return matters A grid with no fresh oranges at all is already done: the answer is 0, not -1. This is the single most common wrong submission on this problem.

  7. Why minutes isn’t off by one The loop condition includes fresh > 0, so the final iteration — the one that would run after the last orange rots and enqueue nothing — never executes. Without that guard you’d return minutes + 1.

3. The Dry Run

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

Seed: queue = [(0,0)], fresh = 6

Minute Queue at start (size) Newly rotted fresh after minutes
1 [(0,0)] (1) (0,1), (1,0) 4 1
2 [(0,1),(1,0)] (2) (0,2), (1,1) 2 2
3 [(0,2),(1,1)] (2) (2,1) 1 3
4 [(2,1)] (1) (2,2) 0 4

fresh == 0 → loop exits → return 4 ✓

Grid state per minute:

min 0      min 1      min 2      min 3      min 4
2 1 1      2 2 1      2 2 2      2 2 2      2 2 2
1 1 0      2 1 0      2 2 0      2 2 0      2 2 0
0 1 1      0 1 1      0 1 1      0 2 1      0 2 2

4. Java Solution

Brute Force (BFS per source — correct but wasteful)

// For every rotten cell, BFS the grid recording distance to each fresh cell,
// keep the minimum distance per fresh cell, then take the max over all fresh cells.
// Time O(R * m * n) where R = number of rotten oranges. Skipped in full —
// the point is that multi-source BFS collapses all R passes into one.

Optimal (Multi-Source BFS)

class Solution {
    private static final int[][] DIRS = {{1,0}, {-1,0}, {0,1}, {0,-1}};

    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        int fresh = 0;

        // PASS 1: seed every rotten cell + count fresh
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) queue.offer(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }

        if (fresh == 0) return 0;         // nothing to rot → 0 minutes, NOT -1

        int minutes = 0;
        while (!queue.isEmpty() && fresh > 0) {
            int size = queue.size();      // freeze: everything that rotted last minute
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                for (int[] d : DIRS) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                    if (grid[nr][nc] != 1) continue;          // empty or already rotten

                    grid[nr][nc] = 2;     // mark WHEN ENQUEUED — prevents double-counting
                    fresh--;
                    queue.offer(new int[]{nr, nc});
                }
            }
            minutes++;                    // one full level = one minute
        }

        return fresh == 0 ? minutes : -1; // leftovers are unreachable
    }
}

Time O(m·n) — every cell enqueued at most once · Space O(m·n) for the queue

5. The “Java vs. Others” Edge

  • ArrayDeque as the BFS queue, never LinkedList. Both implement Queue, but ArrayDeque is a circular array — no per-element node allocation, far better cache locality. LinkedList is what old tutorials show; ArrayDeque is what the JDK docs recommend.
  • int[] as the coordinate, not a Point class or a String key. new int[]{r, c} is one small allocation with no boxing. Encoding as "r,c" strings means hashing and parsing on every access — a real slowdown and a common junior habit. An even tighter option: encode as a single int (r * cols + c) and decode with / and %.
  • static final int[][] DIRS — hoisted out of the method so the array isn’t reallocated on every call, and it names the intent. This is the standard Java idiom for grid neighbours.
  • Mutating the input grid as the visited set — legal here and O(1) space beyond the queue. In production you’d copy first; in an interview, say “I’m mutating the input as my visited marker; I’d defensively copy if the caller needs it preserved.”
  • offer/poll return sentinels, add/remove throw. Prefer the sentinel pair with an isEmpty() guard — no exception handling in the hot loop.

6. Complexity Summary

Approach Time Space Notes
BFS per rotten source O(R·m·n) O(m·n) Recomputes the same distances R times
Multi-source BFS O(m·n) O(m·n) Single pass; each cell enqueued once
DFS ✗ — Gives a time, not the minimum — wrong tool

7. Edge Cases & Follow-Ups

Case Expected Why it trips people
[[0]] 0 No fresh oranges → done at minute 0, not -1
[[2,2]] 0 All rotten already
[[1]] -1 Fresh with no source ever
[[2,1,1],[0,1,1],[1,0,1]] -1 Bottom-left 1 is walled off by 0s
[[1,2]] 1 Single-step spread

Follow-ups to expect

  • 8-directional spread? → add the 4 diagonals to DIRS. Nothing else changes.
  • Different oranges rot at different rates? → weighted edges, so BFS no longer works; switch to Dijkstra with a PriorityQueue.
  • Which orange rotted last? → track the cell popped on the final level.
  • Huge sparse grid? → the queue only ever holds the frontier, so memory stays O(frontier).
# Problem Difficulty Sources seeded
LC 542 01 Matrix Medium every 0 cell
LC 286 Walls and Gates Medium every gate
LC 1162 As Far from Land as Possible Medium every land cell
LC 417 Pacific Atlantic Water Flow Medium every ocean-edge cell (two BFS runs)
LC 200 Number of Islands Medium single-source BFS/DFS per island
LC 127 Word Ladder Hard BFS on an implicit graph