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.
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.
1 <= grid rows, cols <= 10grid[i][j] is 0, 1, or 2This is BFS starting from MULTIPLE sources simultaneously — every initially-rotten orange starts in the queue at the same time, not one at a time.
Processing the BFS level by level (like Binary Tree Level Order Traversal's levelSize snapshot technique) naturally tracks elapsed minutes — one level = one minute.
Count fresh oranges up front; if any remain unreached after BFS completes, the answer is -1.
public int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int freshCount = 0;
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}); // seed with ALL initially-rotten oranges at once
else if (grid[r][c] == 1) freshCount++;
}
int minutes = 0;
int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty() && freshCount > 0) {
int levelSize = queue.size(); // one full minute's worth of spread
for (int i = 0; i < levelSize; i++) {
int[] cell = queue.poll();
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) {
grid[nr][nc] = 2;
freshCount--;
queue.offer(new int[]{nr, nc});
}
}
}
minutes++;
}
return freshCount == 0 ? minutes : -1;
}Time: O(rows * cols) · Space: O(rows * cols)