Rotting Oranges
Problem
Given a grid where each cell is 0 (empty), 1 (fresh orange), or 2 (rotten orange), every minute any fresh orange adjacent (4-directionally) to a rotten one becomes rotten. Return the minimum minutes until no fresh orange remains, or -1 if impossible.
Examples
Example 1
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: Rot spreads outward from the single rotten orange, reaching every fresh orange after 4 minutes.
Example 2
Input: grid = [[0,2]]
Output: 0
Explanation: No fresh oranges exist — 0 minutes needed.
Constraints
- •
1 <= grid rows, cols <= 10 - •
grid[i][j] is 0, 1, or 2
Hints
Hint 1
This is BFS starting from MULTIPLE sources simultaneously — every initially-rotten orange starts in the queue at the same time, not one at a time.
Hint 2
Processing the BFS level by level (like Binary Tree Level Order Traversal's levelSize snapshot technique) naturally tracks elapsed minutes — one level = one minute.
Hint 3
Count fresh oranges up front; if any remain unreached after BFS completes, the answer is -1.
Solutions
public int orangesRottingBruteForce(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
int minutes = 0;
int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
while (true) {
boolean anySpread = false;
List<int[]> newlyRotten = new ArrayList<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 2) {
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] == 1) {
newlyRotten.add(new int[]{nr, nc});
anySpread = true;
}
}
}
}
}
if (!anySpread) break;
for (int[] cell : newlyRotten) grid[cell[0]][cell[1]] = 2;
minutes++;
}
for (int[] row : grid) for (int cell : row) if (cell == 1) return -1;
return minutes;
}Time: O((rows*cols)^2) worst case · Space: O(rows*cols)