A produce warehouse is given a crate raster: 0 empty, 1 fresh orange, 2 already rotten. Rot spreads to 4-adjacent fresh oranges each minute; the SLA is the minutes until none are fresh, or a hard fail if some orange can never rot. The intern, for every fresh cell, ran a BFS to the nearest rotten orange and kept the max hop. A 4×4 fixture in staging returned in milliseconds. A thousand-cell floor in production was still walking when the request timed out — and a crate with no fresh oranges returned -1 because they treated an empty max as unreachable.
Rotting Oranges asks how many minutes until every fresh orange is rotten, or -1 if some never rot. This is an interview writeup, not a layout lecture. The graphs post owns the layout; the BFS post owns the queue. Here we only care about seeding every rotten cell before the first hop, marking when we enqueue, and leftover fresh.
The problem
Given an int[][] grid of 0 (empty), 1 (fresh), and 2 (rotten), each minute every fresh orange that shares an edge with a rotten one becomes rotten. Return the minutes until no 1 remains, or -1 if a fresh orange can never rot. Four directions — up, down, left, right — not diagonals. You may mutate the grid.
2 1 1
1 1 0
0 1 1 → 4
2 1 1
0 1 1
1 0 1 → -1
0 2 → 0
1 → -1First crate: the bottom-right fresh waits four minutes. Second: the bottom-left fresh is boxed in by empty cells. Third: nothing fresh to wait on. Fourth: a lone fresh orange never meets rot.
Note: Empty cells are walls, not air. Rot does not jump a 0. Bounds-check first, then skip anything that is not 1 when spreading. A 4-direction int[][] dirs table is the neighbor list; do not special-case four ifs unless the board asks you to name them.
A nearest-rotten walk from every fresh orange is the honest brute force
For each 1, run a BFS through non-empty cells until you hit a 2, keep the max hop, and fail if any walk never finds rot. Correct. Quadratic.
int orangesRottingRestart(int[][] grid) {
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int minutes = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
int hops = nearestRotten(grid, r, c, dirs);
if (hops < 0) {
return -1;
}
minutes = Math.max(minutes, hops);
}
}
}
return minutes;
}
int nearestRotten(int[][] grid, int sr, int sc, int[][] dirs) {
int m = grid.length;
int n = grid[0].length;
boolean[][] seen = new boolean[m][n];
Deque<int[]> q = new ArrayDeque<>();
q.offer(new int[] { sr, sc });
seen[sr][sc] = true;
int hops = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] cur = q.poll();
if (grid[cur[0]][cur[1]] == 2) {
return hops;
}
for (int[] d : dirs) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) {
continue;
}
if (grid[nr][nc] == 0 || seen[nr][nc]) {
continue;
}
seen[nr][nc] = true;
q.offer(new int[] { nr, nc });
}
}
hops++;
}
return -1;
}At a 4×4 fixture this is a rounding error. On a crate of F fresh cells you restart a walk that can visit every orange cell F times: you paid a full BFS per fresh orange for a question that only needs one walk from every rotten cell at once.
Seed every rotten cell, then one BFS
Scan once. Offer every 2 onto an ArrayDeque and count every 1. That queue is minute 0. Then drain by count: each wave is one minute. When a neighbor is still 1, write it to 2, decrement fresh, and offer. Minutes are the hop count; do not re-derive that here.
2 1 1
1 1 0
0 1 1
seed (0,0) fresh=6 minutes=0
wave 1 rot (0,1), (1,0) fresh=4
wave 2 rot (0,2), (1,1) fresh=2
wave 3 rot (2,1) fresh=1
wave 4 rot (2,2) fresh=0 → 4Four deltas, bounds-check, skip anything that is not fresh. Mutation is allowed, so 1 → 2 is the mark — skip a second boolean[][]. The Java is that walk. Use Deque and ArrayDeque, not java.util.Stack, not ArrayList.remove(0).
int orangesRotting(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Deque<int[]> q = new ArrayDeque<>();
int fresh = 0;
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (grid[r][c] == 2) {
q.offer(new int[] { r, c });
} else if (grid[r][c] == 1) {
fresh++;
}
}
}
int minutes = 0;
while (!q.isEmpty() && fresh > 0) {
int size = q.size();
minutes++;
for (int i = 0; i < size; i++) {
int[] cur = q.poll();
for (int[] d : dirs) {
int nr = cur[0] + d[0];
int nc = cur[1] + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n || grid[nr][nc] != 1) {
continue;
}
grid[nr][nc] = 2;
fresh--;
q.offer(new int[] { nr, nc });
}
}
}
return fresh == 0 ? minutes : -1;
}Time is O(mn) — each cell is offered at most once, and each offered cell looks at four neighbors. Space is O(mn) for the queue when the crate is packed with fruit.
Note: Mark when you enqueue. Write 1 → 2 before offer. Wait until poll and two rotten neighbors both enqueue the same fresh cell, and fresh decrements twice. Seed every 2 before the first wave. One rotten source sequences two simultaneous fronts. If fresh is already 0, return 0. The fresh > 0 guard also stops you from incrementing an extra minute after the last orange rots.
What interviewers usually poke next
- 01 Matrix. Distance from every cell to the nearest
0. Same seed-all-sources BFS; the return is a grid of hops, not one integer. - Pacific Atlantic Water Flow. Multi-source from both ocean borders; keep cells that both walks reach. Same queue, two paints.
- Number of Islands. Count how many times you start a flood. That prompt wants component count; this one wants hop count from every rotten cell at once.
- Read-only grid. If mutation is forbidden, a
boolean[][] seenis the mark. Diagonals are eight deltas — ask before you edit the table.
You are done with this problem when you can say, out loud, why a BFS from each fresh orange is quadratic, why every rotten cell belongs in the queue before the first hop, and why leftover fresh is -1 while no fresh is 0.