85.Rotting Oranges

MediumGraphs · 6/19

Problem

You are given an m x n grid where each cell is 0 (empty), 1 (fresh orange) or 2 (rotten orange). Every minute, each fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes until no fresh orange remains. If some fresh orange can never rot, return -1.

Examples

Input:  grid = [
  [2,1,1],
  [1,1,0],
  [0,1,1]
]
Output: 4
Explanation: The rot spreads from (0,0); the last orange to rot is (2,2), at minute 4.

Input:  grid = [
  [2,1,1],
  [0,1,1],
  [1,0,1]
]
Output: -1
Explanation: The orange at (2,0) is boxed in by the empty cells (1,0) and (2,1), so the rot can never reach it.

Input:  grid = [[0,2]]
Output: 0
Explanation: There are no fresh oranges at minute 0, so no time is needed.

Constraints

m == grid.length, n == grid[i].length
1 <= m, n <= 10
grid[i][j] is 0, 1 or 2

💡 Key Insight

All rotten oranges spread at the same time, one step per minute. That is exactly a multi-source BFS: put every initially rotten orange in the queue as level 0, and each BFS level is one minute. The time at which a fresh orange is first reached is its shortest distance to any rotten source, and the answer is the number of levels needed to reach the last one. Count fresh oranges up front; if any remain afterwards, return -1.

Brute Force (Minute-by-Minute Simulation)

TimeO((m·n)²)SpaceO(m·n)

Intuition

Literally simulate the clock. Each minute, scan the whole grid and collect every fresh orange that has a rotten neighbour. Rot them all after the scan (so an orange rotted this minute cannot spread in the same minute). Stop when a minute produces no change, then check whether any fresh orange is left.

Algorithm

Repeat:
- Scan all cells; collect each 1 that has a neighbour equal to 2.
- If nothing was collected, stop.
- Set every collected cell to 2 and increment minutes.
If any 1 remains, return -1; else return minutes.

Visualization

minute 0     minute 1     minute 2     minute 3     minute 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

Code

java

import java.util.ArrayList;
import java.util.List;

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;
        int minutes = 0;

        while (true) {
            // Collect every fresh orange touching a rotten one
            List<int[]> toRot = new ArrayList<>();
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] == 1 && hasRottenNeighbour(grid, r, c)) {
                        toRot.add(new int[]{r, c});
                    }
                }
            }
            if (toRot.isEmpty()) break;
            for (int[] cell : toRot) {
                grid[cell[0]][cell[1]] = 2; // apply after the scan
            }
            minutes++;
        }

        for (int[] row : grid) {
            for (int cell : row) {
                if (cell == 1) return -1; // unreachable fresh orange
            }
        }
        return minutes;
    }

    private boolean hasRottenNeighbour(int[][] grid, int r, int c) {
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] == 2) {
                return true;
            }
        }
        return false;
    }
}

Complexity

Time: O((m·n)²) — there can be up to m·n minutes (a long snake of oranges), each scanning the full grid.
Space: O(m·n) — the toRot list.

BFS from Each Rotten Orange

TimeO(k·m·n)SpaceO(m·n)

Intuition

The minute at which a fresh orange rots is its shortest distance to the nearest rotten orange (moving only through oranges). Run a separate BFS from every rotten orange, and keep dist[r][c] = the minimum over all sources. The answer is the largest dist among fresh oranges, or -1 if some fresh orange was never reached.

Algorithm

Fill dist with Integer.MAX_VALUE.
For each rotten cell, BFS through fresh cells (1) with its own visited array, setting dist[nr][nc] = min(dist[nr][nc], steps).
For every fresh cell: if dist is still MAX_VALUE return -1; otherwise answer = max(answer, dist).
Return answer (0 if there were no fresh oranges).

Visualization

grid          dist from (0,0)
2 1 1         . 1 2
1 1 0         1 2 .
0 1 1         . 3 4

Only one rotten source here; max over fresh cells = 4.
With k rotten oranges, k separate BFS passes are run and the minimum is kept.

Code

java

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

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;
        int[][] dist = new int[rows][cols];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) bfsFrom(grid, dist, r, c);
            }
        }

        int answer = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] != 1) continue;
                if (dist[r][c] == Integer.MAX_VALUE) return -1; // never reached
                answer = Math.max(answer, dist[r][c]);
            }
        }
        return answer;
    }

    // Single-source BFS through fresh oranges, keeping the best distance per cell
    private void bfsFrom(int[][] grid, int[][] dist, int sr, int sc) {
        int rows = grid.length, cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{sr, sc, 0});
        visited[sr][sc] = true;
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int[] d : DIRS) {
                int nr = cur[0] + d[0], nc = cur[1] + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
                        && !visited[nr][nc] && grid[nr][nc] == 1) {
                    visited[nr][nc] = true;
                    dist[nr][nc] = Math.min(dist[nr][nc], cur[2] + 1);
                    queue.offer(new int[]{nr, nc, cur[2] + 1});
                }
            }
        }
    }
}

Complexity

Time: O(k·m·n) — one full BFS per rotten orange, where k can be up to m·n.
Space: O(m·n) — dist, visited and the queue.

Multi-Source BFSOptimal

TimeO(m·n)SpaceO(m·n)

Intuition

Instead of one BFS per rotten orange, start a single BFS with all rotten oranges in the queue at once. BFS processes the queue level by level, and each level is exactly one minute of simultaneous spreading. Keep a fresh counter: decrement it whenever an orange rots. When the queue drains, fresh == 0 means everything rotted.

Algorithm

Enqueue every 2; count every 1 into fresh.
minutes = 0. While the queue is non-empty and fresh > 0:
- Process exactly queue.size() cells (one minute).
- For each fresh neighbour: set it to 2, fresh--, enqueue it.
- minutes++.
Return fresh == 0 ? minutes : -1.

Dry Run

flowchart TD
    M0["minute 0<br/>queue: (0,0)<br/>fresh = 6"] --> M1["minute 1<br/>rot (1,0), (0,1)<br/>fresh = 4"]
    M1 --> M2["minute 2<br/>rot (1,1), (0,2)<br/>fresh = 2"]
    M2 --> M3["minute 3<br/>rot (2,1)<br/>fresh = 1"]
    M3 --> M4["minute 4<br/>rot (2,2)<br/>fresh = 0"]
    M4 --> R["fresh == 0 → return 4"]

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

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;
        Deque<int[]> queue = new ArrayDeque<>();
        int fresh = 0;

        // All rotten oranges are sources at minute 0
        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++;
            }
        }

        int minutes = 0;
        while (!queue.isEmpty() && fresh > 0) {
            int levelSize = queue.size(); // everything that is rotten at this minute
            for (int i = 0; i < levelSize; 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 && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        fresh--;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}

Complexity

Time: O(m·n) — each cell is enqueued at most once and checks 4 neighbours.
Space: O(m·n) — the queue can hold a large fraction of the grid.

Complexity Comparison

Approach	Time	Space
Brute Force Simulation	O((m·n)²)	O(m·n)
BFS from Each Rotten Orange	O(k·m·n)	O(m·n)
Multi-Source BFS	O(m·n)	O(m·n)

Common Pitfalls

Looping while (!queue.isEmpty()) without the fresh > 0 guard and incrementing minutes after the last level — this over-counts by one, because the final level rots nothing.
Returning -1 when there are no fresh oranges at all; the correct answer is 0 (e.g. [[0,2]] or [[0]]).
Rotting oranges during the scan in the simulation, which lets rot travel several cells in a single minute.
Running separate BFS passes and taking the max instead of the min distance per cell.
Forgetting to check for unreachable fresh oranges at the end.