DSA-097 · FOCUSED PRACTICE
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:4Layers 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:-1The empty middle cell separates the only fresh orange from every source.
Input:
[[0,2]]
Output:0There 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.
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.
No unsaved text changes · 110/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
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.
0 = empty · 1 = fresh · 2 = rotten. Newly marked cells act in the next queue layer.
| 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.
0 = empty · 1 = fresh · 2 = rotten. Newly marked cells act in the next queue layer.
| 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:0Zero rows.
Input:
[[]]
Output:0Zero columns.
Input:
[[1]]
Output:-1Fresh cell without a source.
Input:
[[2,1,2]]
Output:1Two sources share one neighbor.
Input:
[[2,0],[0,1]]
Output:-1Diagonal isolation.
Input:
[[2,1,1,1,2]]
Output:2Several 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.