Back to DSA
Rotting Oranges
mediumA grid contains empty cells (0), fresh items (1), and contaminated items (2). Each minute, any fresh item adjacent (up/down/left/right) to a contaminated item becomes contaminated. Report the minimum number of minutes until every item is contaminated, or -1 if some items can never be reached.
Examples
Example 1:
Input:
grid = [[1,2,1],[1,1,1],[0,1,2]]Output:
2Explanation: Both contaminated cells spread outward; after 2 minutes all fresh items are reached.
Example 2:
Input:
grid = [[2,1,0],[0,1,0],[0,0,1]]Output:
-1Explanation: The item at (2,2) is isolated and cannot be contaminated.
Hints
import java.util.*;
class Solution {
public int orangesRotting(int[][] grid) {
int m = grid.length, n = grid[0].length;
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) queue.offer(new int[]{i, j});
else if (grid[i][j] == 1) fresh++;
}
if (fresh == 0) return 0;
int minutes = 0;
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
fresh--;
queue.offer(new int[]{nr, nc});
}
}
}
minutes++;
}
return fresh == 0 ? minutes - 1 : -1;
}
}Time complexity
O(m * n)Space complexity
O(m * n)