Topics › Graphs › Problems on BFS/DFS

Rotten Oranges

Medium TUF ID 536 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given an n x m grid where each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that is directly up, down, left or right of 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. If there are no fresh oranges to begin with, the answer is 0.

Constraints: 1 ≤ n, m ≤ 10 on LeetCode (the solutions here are linear, so much larger grids are fine too).

Example 1

grid = 2 1 1
       1 1 0
       0 1 1
answer = 4

Minute 1 rots (0,1) and (1,0); minute 2 rots (0,2) and (1,1); minute 3 rots (2,1); minute 4 rots (2,2).

Example 2

grid = 2 1 1
       0 1 1
       1 0 1
answer = -1         // the orange at (2,0) has no orange neighbour at all

The key observation is that rot spreads like a wave, one cell per minute, from all rotten oranges at the same time. The minute in which a fresh orange rots is its distance to the nearest rotten orange, counting steps through orange cells only. The answer is the largest such distance. “Distance, in steps, from the nearest of several sources” is exactly what a breadth-first search computes.

Approach 1: Brute force, simulate minute by minute

Intuition. Do what the statement describes. Each minute, scan the whole grid and collect every fresh orange that has a rotten neighbour. Rot all of them together after the scan, then count one minute. Repeat until a minute rots nothing. If a fresh orange is left at that point, it is unreachable.

Collecting first and applying afterwards is essential. If we rotted each orange the moment we found it, an orange rotted early in the scan would immediately infect the next cell in the same scan, and rot would travel across the grid in a single “minute”.

Algorithm.

1. Copy the grid (the caller’s grid stays untouched).
2. Repeat: build toRot, the list of fresh cells with a rotten 4-neighbour. If it is empty, stop. Otherwise rot them all and increment minutes.
3. If any 1 remains, return -1; else return minutes.

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

static int bruteForce(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    int[][] g = new int[n][];
    for (int i = 0; i < n; i++) g[i] = grid[i].clone();
    int minutes = 0;
    while (true) {
        List<int[]> toRot = new ArrayList<>();
        for (int r = 0; r < n; r++) {
            for (int c = 0; c < m; c++) {
                if (g[r][c] != 1) continue;
                for (int[] d : DIRS) {
                    int nr = r + d[0], nc = c + d[1];
                    if (nr >= 0 && nr < n && nc >= 0 && nc < m && g[nr][nc] == 2) {
                        toRot.add(new int[]{r, c});   // touches an orange that was rotten at the start of this minute
                        break;
                    }
                }
            }
        }
        if (toRot.isEmpty()) break;
        for (int[] p : toRot) g[p[0]][p[1]] = 2;      // apply after the scan, so rot moves one step per minute
        minutes++;
    }
    for (int[] row : g) {
        for (int v : row) if (v == 1) return -1;      // some fresh orange can never be reached
    }
    return minutes;
}

Complexity. Time O((n * m)^2): each minute scans all n * m cells, and there can be up to about n * m minutes (a single winding line of oranges rots one per minute). Space O(n * m) for the copy and the list. For a 10 x 10 grid this is instant, but the work is mostly wasted: each scan re-examines cells that are empty, long rotten or still far from the wave.

Approach 2: Optimal, multi-source BFS

Intuition. Only cells on the edge of the wave can do anything in the next minute, so keep exactly those in a queue. Start with every initially rotten orange in the queue at once: that is the multi-source part, and it is the same as adding one imaginary super-source joined to all of them. Then process the queue level by level. Everything in the queue at the start of a round rotted in the same minute; the fresh neighbours they infect rot in the next minute and form the next level.

Keep a count of fresh oranges. Each infection decrements it. When the BFS stops, a non-zero count means some fresh orange was never reached.

Algorithm.

1. Copy the grid. Enqueue every rotten cell, and count the fresh ones.
2. While the queue is non-empty and fresh > 0: let size be the queue’s size; poll size cells, and for each fresh 4-neighbour, rot it, decrement fresh and enqueue it. Then increment minutes.
3. Return minutes if fresh == 0, otherwise -1.

static int optimal(int[][] grid) {
    int n = grid.length, m = grid[0].length;
    int[][] g = new int[n][];
    for (int i = 0; i < n; i++) g[i] = grid[i].clone();
    Deque<int[]> queue = new ArrayDeque<>();
    int fresh = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (g[r][c] == 2) queue.add(new int[]{r, c});
            else if (g[r][c] == 1) fresh++;
        }
    }
    int minutes = 0;
    while (!queue.isEmpty() && fresh > 0) {
        int size = queue.size();                      // everything in the queue rotted at the same minute
        for (int k = 0; k < size; k++) {
            int[] cell = queue.poll();
            for (int[] d : DIRS) {
                int nr = cell[0] + d[0], nc = cell[1] + d[1];
                if (nr < 0 || nr >= n || nc < 0 || nc >= m || g[nr][nc] != 1) continue;
                g[nr][nc] = 2;                        // rot it now so no other cell enqueues it again
                fresh--;
                queue.add(new int[]{nr, nc});
            }
        }
        minutes++;
    }
    return fresh == 0 ? minutes : -1;
}

Dry run on example 1 (cells as (row, col)):

The loop stops because fresh reached 0, and the answer is 4.

Why the fresh > 0 condition? Without it, the round that processes the last oranges to rot (here (2,2)) would run too, find nothing new, and still increment minutes, giving 5. Stopping as soon as nothing is fresh avoids that off-by-one. It also gives 0 for free when there are no fresh oranges initially: the loop never runs.

Why rot on enqueue? Setting g[nr][nc] = 2 the moment a cell is added plays the role of a visited mark. Two rotten neighbours of the same fresh orange in the same round cannot both enqueue it, and it is never counted twice in fresh.

Complexity. Time O(n * m): each cell enters the queue at most once and checks four neighbours. Space O(n * m) for the copy and the queue.

Edge cases and pitfalls

• No fresh oranges. [[0, 2]] and [[0]] both return 0, even though there is nothing to wait for. Return 0, not -1.
• Fresh oranges but no rotten one. [[1]] returns -1; the queue starts empty.
• Empty cells block the spread. In [[1, 0, 2]] the empty cell separates the two oranges, so the answer is -1. Rot also never travels diagonally.
• Several sources. [[2, 1, 1, 1, 2]] takes 2 minutes, not 4, because the two waves meet in the middle. Starting a separate BFS from each rotten orange and taking the maximum would be wrong as well as slow; the sources must start together.
• Counting minutes per level, not per cell. Incrementing minutes for every polled cell gives a far too large answer. One round of the size loop is one minute.
• Mutating the input. Both methods work on a copy, and the tests check that the grid passed in is unchanged.

Related problems

• Traversal Techniques explains level-by-level BFS, used here with many starting points.
• Distance of nearest cell having one is the same multi-source BFS, reporting every cell’s distance.
• Flood fill algorithm spreads from a single cell without timing.
• Connected Components Problem in Matrix uses the same grid-neighbour mechanics to count islands.