DSA-097 · Multi-source breadth-first search

Rotting Oranges

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 19990 deterministic checks. Learner drafts are not executed.

Understand the problem

Each grid cell is empty (0), fresh (1), or rotten (2). At each minute, every orange rotten at the start of that minute rots its orthogonally adjacent fresh neighbors simultaneously. Return the minimum minutes until no fresh orange remains, or -1 if some can never rot.

Input is a non-null rectangular int[][] with 0–100 rows and 0–100 columns, containing only 0,1,2. Rows are non-null and equally sized. Malformed input is outside the contract.
Empty grid, zero-column grid, or no fresh oranges returns 0. Empty cells block propagation; diagonal contact does not count.
Both implementations mutate reachable fresh cells to 2, including when returning -1. Unreachable fresh cells remain 1. Clone every row first if the caller needs the original grid.

Examples

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Layers reached at minutes 1,2,3,4 exhaust the six fresh oranges; the bottom-right orange is farthest from the initial source.
Input: [[2,0,1]]
Output: -1
The empty middle cell separates the only fresh orange from every source.
Input: [[0,2]]
Output: 0
There are no fresh oranges at minute zero.

Before you start

Matrix bounds and four-direction adjacency
Queue discovery versus processing
BFS layers and shortest unweighted paths

Recognize the structure

The simultaneous spread has unit-time edges and several initial sources. The answer is the largest shortest distance from any source to a fresh cell, provided every fresh cell is reachable. DFS discovery order does not encode arrival time. Weighted spread would require another shortest-path method.

Try before revealing

Hint 1

Imagine all initial rotten cells as one combined starting frontier. What graph edge represents one minute?

Hint 2

Newly discovered cells should act in the next minute. How do you keep the two frontiers separate in one queue?

Hint 3

Freeze the queue size for each layer and mark a neighbor rotten before enqueueing it. Track remaining fresh cells.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Simulate each minute with a full scan

Scan all fresh cells, marking those adjacent to a cell already rotten at the start of the minute in a separate boolean matrix. Apply all marks only after the scan. For [2,1,1], the scans produce [2,2,1] at minute 1 and [2,2,2] at minute 2. Stop with -1 if fresh cells remain but no marks are made. If propagation takes T rounds, full rescans cost O(RC(T+1)); T can be O(RC), so the worst case is O((RC)^2), with O(RC) temporary storage.

Improve the baseline

Only new boundaries matter

After a cell has offered infection to its neighbors once, rescanning it adds no work. Put every initial rotten cell in one queue and count fresh cells.

Freeze the minute boundary

Take layerSize=queue.size() at the beginning of a minute. Process exactly that many cells, while appending newly rotten neighbors for the next minute. Otherwise [2,1,1] could be consumed in a single minute.

Claim neighbors on discovery

Set a fresh neighbor to 2 before enqueueing and decrement fresh once. Competing sources can see the same neighbor, but only the first sees a 1. Return minutes if fresh is zero, else -1 when the queue drains.

Why it is correct

Initialization

The queue contains all sources at time 0; fresh counts exactly the grid cells with value 1.

Preservation

At the start of each active round, the queue is precisely the frontier for the current elapsed time. Its fresh neighbors have minimum arrival time one greater: any shorter route would have discovered them in an earlier frontier. Discovery marks them immediately, so each cell enters the queue at most once.

Termination and result

Each active round either consumes a finite frontier or discovers new cells. At most RC cells can enter the queue. If fresh becomes zero, the last completed round is the maximum needed arrival time. If the frontier empties while fresh remains, those cells have no path from any source and -1 is required.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

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

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

    public static int orangesRotting(int[][] grid) {
        int rows = grid.length;
        if (rows == 0 || grid[0].length == 0) return 0;
        int cols = grid[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        int fresh = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) queue.addLast(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        }
        int minutes = 0;
        while (fresh > 0 && !queue.isEmpty()) {
            int layerSize = queue.size();
            for (int i = 0; i < layerSize; i++) {
                int[] cell = queue.removeFirst();
                for (int[] d : DIRECTIONS) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 1) continue;
                    grid[nr][nc] = 2;
                    fresh--;
                    queue.addLast(new int[]{nr, nc});
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }

    public static int baseline(int[][] grid) {
        int rows = grid.length;
        if (rows == 0 || grid[0].length == 0) return 0;
        int cols = grid[0].length, minutes = 0;
        while (true) {
            boolean[][] change = new boolean[rows][cols];
            int fresh = 0, newlyRotten = 0;
            for (int r = 0; r < rows; r++) {
                for (int c = 0; c < cols; c++) {
                    if (grid[r][c] != 1) continue;
                    fresh++;
                    for (int[] d : DIRECTIONS) {
                        int nr = r + d[0], nc = c + d[1];
                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 2) {
                            change[r][c] = true;
                            break;
                        }
                    }
                    if (change[r][c]) newlyRotten++;
                }
            }
            if (fresh == 0) return minutes;
            if (newlyRotten == 0) return -1;
            for (int r = 0; r < rows; r++)
                for (int c = 0; c < cols; c++)
                    if (change[r][c]) grid[r][c] = 2;
            minutes++;
        }
    }
}

Read the meaningful blocks

Initialize sources and fresh count

Scan the grid once; do not choose one source and repeat BFS independently.

Process a fixed-size layer

layerSize separates the current minute from work appended during it. Increment minutes once per processed round while fresh remains.

Discover once

Check bounds and value==1. Mutate before enqueueing to prevent duplicate claims and incorrect fresh counts.

Return reachability result

A drained queue does not by itself mean success. The remaining fresh count distinguishes impossible cases.

Complexity

Initialization scans RC cells and each cell is enqueued at most once; four neighbors are considered per dequeue. Time is O(RC). Queue storage is O(RC) in the worst case, including many initial sources.

The grid is mutated, which avoids a separate visited matrix but does not remove queue storage. Copying for a non-mutating wrapper costs O(RC) additional time and space. Full-scan simulation costs O(RC(T+1)) time and O(RC) auxiliary storage.

Exact-state walkthroughs

Reveal normal and boundary traces

Four minute propagation

Input: [[2,1,1],[1,1,0],[0,1,1]] · Result: 4

Step 1 of 16: Enqueue every initial source.

The initial frontier has arrival time zero.

Grid after this step

211

110

011

0 = empty · 1 = fresh · 2 = rotten. Newly marked cells act in the next queue layer.

State after this step
Variable	Value
grid	`[[2,1,1],[1,1,0],[0,1,1]]`
queue	`[[0,0]]`
fresh	`6`
minutes	`0`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Deque;
 3 
 4 public final class Solution {
 5     private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 6 
 7     public static int orangesRotting(int[][] grid) {
 8         int rows = grid.length;
 9         if (rows == 0 || grid[0].length == 0) return 0;
10         int cols = grid[0].length;
11         Deque<int[]> queue = new ArrayDeque<>();
12         int fresh = 0;
13         for (int r = 0; r < rows; r++) {
14             for (int c = 0; c < cols; c++) {
15                 if (grid[r][c] == 2) queue.addLast(new int[]{r, c});
16                 else if (grid[r][c] == 1) fresh++;
17             }
18         }
19         int minutes = 0;
20         while (fresh > 0 && !queue.isEmpty()) {
21             int layerSize = queue.size();
22             for (int i = 0; i < layerSize; i++) {
23                 int[] cell = queue.removeFirst();
24                 for (int[] d : DIRECTIONS) {
25                     int nr = cell[0] + d[0], nc = cell[1] + d[1];
26                     if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 1) continue;
27                     grid[nr][nc] = 2;
28                     fresh--;
29                     queue.addLast(new int[]{nr, nc});
30                 }
31             }
32             minutes++;
33         }
34         return fresh == 0 ? minutes : -1;
35     }
36 
37     public static int baseline(int[][] grid) {
38         int rows = grid.length;
39         if (rows == 0 || grid[0].length == 0) return 0;
40         int cols = grid[0].length, minutes = 0;
41         while (true) {
42             boolean[][] change = new boolean[rows][cols];
43             int fresh = 0, newlyRotten = 0;
44             for (int r = 0; r < rows; r++) {
45                 for (int c = 0; c < cols; c++) {
46                     if (grid[r][c] != 1) continue;
47                     fresh++;
48                     for (int[] d : DIRECTIONS) {
49                         int nr = r + d[0], nc = c + d[1];
50                         if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 2) {
51                             change[r][c] = true;
52                             break;
53                         }
54                     }
55                     if (change[r][c]) newlyRotten++;
56                 }
57             }
58             if (fresh == 0) return minutes;
59             if (newlyRotten == 0) return -1;
60             for (int r = 0; r < rows; r++)
61                 for (int c = 0; c < cols; c++)
62                     if (change[r][c]) grid[r][c] = 2;
63             minutes++;
64         }
65     }
66 }
67

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Enqueue every initial source.
The initial frontier has arrival time zero.
grid
[[2,1,1],[1,1,0],[0,1,1]]
queue
[[0,0]]
fresh
6
minutes
0
Freeze this minute’s frontier.
Only these layerSize cells act in this round.
grid
[[2,1,1],[1,1,0],[0,1,1]]
queue
[[0,0]]
layerSize
1
fresh
6
minutes
0
Discover [1,0] from [0,0]; it acts next round.
The cell is marked on discovery, so no second source can claim it.
grid
[[2,1,1],[2,1,0],[0,1,1]]
queue
[[1,0]]
fresh
5
minutes
0
arrivalMinute
1
Discover [0,1] from [0,0]; it acts next round.
The cell is marked on discovery, so no second source can claim it.
grid
[[2,2,1],[2,1,0],[0,1,1]]
queue
[[1,0],[0,1]]
fresh
4
minutes
0
arrivalMinute
1
Complete one minute.
The queue is now the next time frontier.
grid
[[2,2,1],[2,1,0],[0,1,1]]
queue
[[1,0],[0,1]]
fresh
4
minutes
1
Freeze this minute’s frontier.
Only these layerSize cells act in this round.
grid
[[2,2,1],[2,1,0],[0,1,1]]
queue
[[1,0],[0,1]]
layerSize
2
fresh
4
minutes
1
Discover [1,1] from [1,0]; it acts next round.
The cell is marked on discovery, so no second source can claim it.
grid
[[2,2,1],[2,2,0],[0,1,1]]
queue
[[0,1],[1,1]]
fresh
3
minutes
1
arrivalMinute
2
Discover [0,2] from [0,1]; it acts next round.
The cell is marked on discovery, so no second source can claim it.
grid
[[2,2,2],[2,2,0],[0,1,1]]
queue
[[1,1],[0,2]]
fresh
2
minutes
1
arrivalMinute
2
Complete one minute.
The queue is now the next time frontier.
grid
[[2,2,2],[2,2,0],[0,1,1]]
queue
[[1,1],[0,2]]
fresh
2
minutes
2
Freeze this minute’s frontier.
Only these layerSize cells act in this round.
grid
[[2,2,2],[2,2,0],[0,1,1]]
queue
[[1,1],[0,2]]
layerSize
2
fresh
2
minutes
2
Discover [2,1] from [1,1]; it acts next round.
The cell is marked on discovery, so no second source can claim it.
grid
[[2,2,2],[2,2,0],[0,2,1]]
queue
[[0,2],[2,1]]
fresh
1
minutes
2
arrivalMinute
3
Complete one minute.
The queue is now the next time frontier.
grid
[[2,2,2],[2,2,0],[0,2,1]]
queue
[[2,1]]
fresh
1
minutes
3
Freeze this minute’s frontier.
Only these layerSize cells act in this round.
grid
[[2,2,2],[2,2,0],[0,2,1]]
queue
[[2,1]]
layerSize
1
fresh
1
minutes
3
Discover [2,2] from [2,1]; it acts next round.
The cell is marked on discovery, so no second source can claim it.
grid
[[2,2,2],[2,2,0],[0,2,2]]
queue
[[2,2]]
fresh
0
minutes
3
arrivalMinute
4
Complete one minute.
The queue is now the next time frontier.
grid
[[2,2,2],[2,2,0],[0,2,2]]
queue
[[2,2]]
fresh
0
minutes
4
Return the contract result.
The result follows from the completed state and the declared contract.
result
4

Unreachable fresh cell

Input: [[2,0,1]] · Result: -1

Step 1 of 4: Enqueue every initial source.

The initial frontier has arrival time zero.

Grid after this step

201

0 = empty · 1 = fresh · 2 = rotten. Newly marked cells act in the next queue layer.

State after this step
Variable	Value
grid	`[[2,0,1]]`
queue	`[[0,0]]`
fresh	`1`
minutes	`0`

See the affected Java block

 1 import java.util.ArrayDeque;
 2 import java.util.Deque;
 3 
 4 public final class Solution {
 5     private static final int[][] DIRECTIONS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
 6 
 7     public static int orangesRotting(int[][] grid) {
 8         int rows = grid.length;
 9         if (rows == 0 || grid[0].length == 0) return 0;
10         int cols = grid[0].length;
11         Deque<int[]> queue = new ArrayDeque<>();
12         int fresh = 0;
13         for (int r = 0; r < rows; r++) {
14             for (int c = 0; c < cols; c++) {
15                 if (grid[r][c] == 2) queue.addLast(new int[]{r, c});
16                 else if (grid[r][c] == 1) fresh++;
17             }
18         }
19         int minutes = 0;
20         while (fresh > 0 && !queue.isEmpty()) {
21             int layerSize = queue.size();
22             for (int i = 0; i < layerSize; i++) {
23                 int[] cell = queue.removeFirst();
24                 for (int[] d : DIRECTIONS) {
25                     int nr = cell[0] + d[0], nc = cell[1] + d[1];
26                     if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] != 1) continue;
27                     grid[nr][nc] = 2;
28                     fresh--;
29                     queue.addLast(new int[]{nr, nc});
30                 }
31             }
32             minutes++;
33         }
34         return fresh == 0 ? minutes : -1;
35     }
36 
37     public static int baseline(int[][] grid) {
38         int rows = grid.length;
39         if (rows == 0 || grid[0].length == 0) return 0;
40         int cols = grid[0].length, minutes = 0;
41         while (true) {
42             boolean[][] change = new boolean[rows][cols];
43             int fresh = 0, newlyRotten = 0;
44             for (int r = 0; r < rows; r++) {
45                 for (int c = 0; c < cols; c++) {
46                     if (grid[r][c] != 1) continue;
47                     fresh++;
48                     for (int[] d : DIRECTIONS) {
49                         int nr = r + d[0], nc = c + d[1];
50                         if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 2) {
51                             change[r][c] = true;
52                             break;
53                         }
54                     }
55                     if (change[r][c]) newlyRotten++;
56                 }
57             }
58             if (fresh == 0) return minutes;
59             if (newlyRotten == 0) return -1;
60             for (int r = 0; r < rows; r++)
61                 for (int c = 0; c < cols; c++)
62                     if (change[r][c]) grid[r][c] = 2;
63             minutes++;
64         }
65     }
66 }
67

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Enqueue every initial source.
The initial frontier has arrival time zero.
grid
[[2,0,1]]
queue
[[0,0]]
fresh
1
minutes
0
Freeze this minute’s frontier.
Only these layerSize cells act in this round.
grid
[[2,0,1]]
queue
[[0,0]]
layerSize
1
fresh
1
minutes
0
Complete one minute.
The queue is now the next time frontier.
grid
[[2,0,1]]
queue
[]
fresh
1
minutes
1
Return the contract result.
The result follows from the completed state and the declared contract.
result
-1

Test the contract

Input: []
Output: 0
Zero rows.
Input: [[]]
Output: 0
Zero columns.
Input: [[1]]
Output: -1
Fresh cell without a source.
Input: [[2,1,2]]
Output: 1
Two sources share one neighbor.
Input: [[2,0],[0,1]]
Output: -1
Diagonal isolation.
Input: [[2,1,1,1,2]]
Output: 2
Several sources shorten arrival times.

Common mistakes and counterexamples

Start BFS from only one rotten cell

Counterexample: [2,1,1,1,2] needs 2 minutes; one-source BFS can report 3.

Enqueue all initial sources at time 0.

Process new cells in the same minute

Counterexample: [2,1,1] must return 2, not 1.

Freeze layerSize before dequeuing.

Use diagonal spread

Counterexample: [[2,0],[0,1]] is impossible.

Use four orthogonal direction vectors only.

Mark only when removing from the queue

Counterexample: [2,1,2] has one fresh orange shared by two sources.

Mark on enqueue so fresh decrements once.

Return minutes whenever the queue empties

Counterexample: [2,0,1] still has fresh cells.

Check fresh==0 before returning a duration.

Follow-ups

Return each cell’s infection time.

Initialize source distances to 0, unreached fresh cells to -1, and write distance[current]+1 on discovery. The answer is the maximum finite fresh-cell distance unless any fresh cell is unreachable.

Every cell has a different infection delay.

FIFO layers no longer represent elapsed time. Model nonnegative edge/entry costs and use a priority queue for Dijkstra; define whether delay belongs to the entering cell or outgoing edge.

Do not mutate the input.

Use a separate distance/visited matrix or deep-clone rows. An outer-array clone alone shares rows and therefore still mutates the caller’s grid.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 110/20,000 characters

Self-review

I can explain the fixed-size layer boundary.I mark on discovery and count each fresh cell once.I check remaining fresh cells and document grid mutation.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-14 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.