#994 Rotting Oranges
frequently reported atFlipkartAmazonSamsungWalmartInfosysMicrosoft
the problem
In plain words
Cells are 0 (empty), 1 (fresh orange) or 2 (rotten). Every minute, fresh oranges next to a rotten one (4 directions) rot. Return the minutes until no fresh orange is left, or -1 if that's impossible.
in grid = [[2,1,1],[1,1,0],[0,1,1]]
out 4
in grid = [[2,1,1],[0,1,1],[1,0,1]]
out -1
The bottom-left orange is never next to a rotten one.
in grid = [[0,2]]
out 0
No fresh oranges at minute 0.
- 1 ≤ m, n ≤ 10
- grid[i][j] ∈ {0, 1, 2}
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMulti-source BFS
All rotten oranges spread at the same time — so start BFS from all of them at once. Each BFS level is one minute.
solutions
From brute force to optimal
Each minute, rescan the whole grid to find fresh oranges touching rotten ones; rot them together.
- Collect all fresh cells next to a rotten cell.
- If none, stop; else rot them all and minutes++.
- At the end, any fresh left → -1.
Up to m·n minutes (a long snake), each rescanning all m·n cells.
The list of cells to rot this minute.
class Solution { /** Replays the rot minute by minute, rescanning the whole grid each minute. */ public int orangesRotting(int[][] grid) { int rows = grid.length, cols = grid[0].length, minutes = 0; while (true) { List<int[]> toRot = new ArrayList<>(); for (int r = 0; r < rows; r++) for (int c = 0; c < cols; c++) if (grid[r][c] == 1 && touchesRotten(grid, r, c)) toRot.add(new int[] {r, c}); if (toRot.isEmpty()) break; for (int[] cell : toRot) grid[cell[0]][cell[1]] = 2; // apply all at once: same minute minutes++; } for (int[] row : grid) for (int v : row) if (v == 1) return -1; // someone was never reached return minutes; } private boolean touchesRotten(int[][] g, int r, int c) { return (r > 0 && g[r - 1][c] == 2) || (r + 1 < g.length && g[r + 1][c] == 2) || (c > 0 && g[r][c - 1] == 2) || (c + 1 < g[0].length && g[r][c + 1] == 2); }}Enqueue every rotten orange first, count fresh ones, then BFS level by level.
- Enqueue all 2s; count the 1s.
- While the queue isn't empty and fresh > 0: minutes++, process exactly
queue.size()cells. - Rot each fresh neighbour, fresh--, enqueue it.
- Return fresh == 0 ? minutes : -1.
Every cell enters the queue at most once; each checks 4 neighbours.
The queue can hold many cells at once.
class Solution { public int orangesRotting(int[][] grid) { int rows = grid.length, cols = grid[0].length, fresh = 0; Deque<int[]> queue = new ArrayDeque<>(); 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; int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; while (!queue.isEmpty() && fresh > 0) { minutes++; for (int size = queue.size(); size > 0; size--) { // exactly one BFS level = one minute int[] cell = queue.poll(); for (int[] d : dirs) { int nr = cell[0] + d[0], nc = cell[1] + d[1]; if (nr < 0 || nc < 0 || nr >= rows || nc >= cols || grid[nr][nc] != 1) continue; grid[nr][nc] = 2; fresh--; queue.offer(new int[] {nr, nc}); } } } return fresh == 0 ? minutes : -1; }}Dry run
in the room
How to say it in the interview
talk track
- Say: "It's multi-source BFS — like one BFS from a virtual node connected to every rotten orange."
- Explain the
sizesnapshot: it separates minute k from minute k+1. - Mention the
fresh > 0loop guard — without it you count one extra minute at the end.
traps
- Running a separate BFS from each rotten orange and taking the max — wrong (spreads overlap) and slower.
- Returning minutes when fresh oranges are unreachable.
what they ask next
Follow-ups
Walls and Gates / 01 Matrix (LC 286 / 542)?
Same pattern: seed the queue with every gate/zero, BFS outward, write the distance into each cell on first visit. Both are worked below.
before you submit
Edge cases to test
- No fresh oranges at all → 0, even if there are no rotten ones.
- Fresh oranges but no rotten one → -1.
- A fresh orange walled off by empty cells → -1.
- Without the
fresh > 0guard you count one extra minute after the last orange rots.
practise next
Similar problems
- #54201 MatrixMediumin Graphs
- #286Walls and GatesMediumin GraphsLeetCode Premium
- #1091Shortest Path in Binary MatrixMediumin Graphs