Find minimum time for all oranges to rot. Rotten oranges spread to adjacent fresh ones each minute.
Input: grid=[[2,1,1],[1,1,0],[0,1,1]] → Output: 4
Input: grid=[[2,1,1],[0,1,1],[1,0,1]] → Output: -1
Multi-source BFS from all initially rotten oranges. Count minutes and fresh oranges remaining.
- Add all rotten orange positions to BFS queue, count fresh oranges
- BFS layer by layer (each layer = 1 minute)
- For each rotten orange: rot adjacent fresh oranges, decrement fresh count
- After BFS: if fresh > 0 return -1, else return minutes
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length, fresh = 0, minutes = 0;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) queue.add(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty() && fresh > 0) {
minutes++;
for (int size = queue.size(); size > 0; size--) {
int[] cur = queue.poll();
for (int[] d : dirs) {
int ni = cur[0]+d[0], nj = cur[1]+d[1];
if (ni>=0 && ni<m && nj>=0 && nj<n && grid[ni][nj]==1) {
grid[ni][nj]=2; fresh--; queue.add(new int[]{ni,nj});
}
}
}
}
return fresh == 0 ? minutes : -1;
}
- Time Complexity: O(m*n)
- Space Complexity: O(m*n)