Skip to content
DSA Grind
All 26 sections

Rotting Oranges (LC 994)

ProblemMediumLeetCode 994Updated
On this page

Pattern: Multi-Source BFS (Simultaneous Spread) Difficulty: Medium Key Concept: All initially rotten oranges spread their rot at the same time. Push every rotten cell into the BFS queue at once, then do level-order BFS — each level = 1 minute.

Problem Statement

A 2-D grid of values:

  • 0 = empty
  • 1 = fresh orange
  • 2 = rotten orange

Each minute, any fresh orange adjacent (4-directionally) to a rotten one becomes rotten. Return the minimum minutes until no fresh orange remains, or -1 if some fresh orange is unreachable.

Example

  • grid = [[2,1,1],[1,1,0],[0,1,1]] → 4
  • grid = [[2,1,1],[0,1,1],[1,0,1]] → -1
  • grid = [[0,2]] → 0

1. Algorithm & Pseudocode

queue = all initial rotten cells
fresh = count of 1s

if fresh == 0: return 0

minutes = 0
while queue not empty AND fresh > 0:
    size = queue.size()
    for i in 0..size-1:
        (r, c) = queue.poll()
        for each 4-direction neighbor (nr, nc):
            if in bounds and grid[nr][nc] == 1:
                grid[nr][nc] = 2
                fresh--
                queue.offer((nr, nc))
    minutes++

return fresh == 0 ? minutes : -1

2. Step-by-Step Analysis

Why multi-source BFS The spread is simultaneous — every existing rotten orange contaminates a neighbor in the same minute. By pushing all initial rotten cells before starting BFS, level k of the BFS = time k after start.

Why count fresh If after BFS some fresh oranges remain (unreachable from any rotten source), return -1. Saves a final grid scan.

Why size = queue.size() outer loop We must process all cells reached at this minute before incrementing time.

Edge case — no fresh oranges initially: return 0.

ASCII Trace for [[2,1,1],[1,1,0],[0,1,1]]

initial rotten: {(0,0)}    fresh = 6
minute 1: spread to (0,1),(1,0)     fresh = 4
minute 2: spread to (0,2),(1,1)     fresh = 2
minute 3: spread to (2,1)           fresh = 1
minute 4: spread to (2,2)           fresh = 0
return 4

3. Java Solution

class Solution {
    private static final int[][] DIRS = {{0,1},{1,0},{0,-1},{-1,0}};
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length, fresh = 0;
        Queue<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) fresh++;
                else if (grid[r][c] == 2) q.offer(new int[]{r, c});
            }

        if (fresh == 0) return 0;

        int minutes = 0;
        while (!q.isEmpty() && fresh > 0) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] cur = q.poll();
                for (int[] d : DIRS) {
                    int nr = cur[0] + d[0], nc = cur[1] + d[1];
                    if (nr >= 0 && nc >= 0 && nr < m && nc < n && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        fresh--;
                        q.offer(new int[]{nr, nc});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}

Time: (O(m \cdot n)) Space: (O(m \cdot n)) for the queue worst case

4. The “Java vs. Others” Edge

  • static final int[][] DIRS = {...} is the cleanest way to encode 4-neighbors in Java.
  • We mutate the grid in place (set to 2) — saves a boolean[][] visited.
  • The pattern of “push all sources, then BFS by level” appears in many problems: walls and gates (LC 286), 01 matrix (LC 542), shortest bridge (LC 934).

5. Complexity Summary

Approach Time Space Notes
Multi-BFS O(m·n) O(m·n) Cleanest; preserves true min
DFS infeasible — Can’t model simultaneous spread