BFS. Time=O(n), space=O(n), where n is the size of the grid.
class Solution {
public int orangesRotting(int[][] grid) {
Queue<int[]> queue = new LinkedList<>();
int freshOranges = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 2) {
queue.offer(new int[]{i, j});
} else if (grid[i][j] == 1) {
freshOranges ++;
}
}
}
int minutes = 0;
int[][] directions = {`{-1, 0}, {1, 0}, {0, -1}, {0, 1}`};
while (!queue.isEmpty()) {
if (freshOranges == 0) { // important!
break;
}
int size = queue.size();
for (int i = 0; i < size; i++) {
int[] orange = queue.poll();
for (int[] direction : directions) {
int row = orange[0] + direction[0];
int col = orange[1] + direction[1];
if (row >= 0 && col >= 0 && row < grid.length && col < grid[0].length) {
if (grid[row][col] == 1) {
grid[row][col] = 2;
freshOranges --;
queue.offer(new int[]{row, col});
}
}
}
}
minutes ++;
}
return freshOranges == 0 ? minutes : -1;
}
}