/**
* 994. Rotting Oranges
*
* You are given an m x n grid where each cell can have one of three values:
*
* 0 representing an empty cell,
* 1 representing a fresh orange, or
* 2 representing a rotten orange.
* Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
*
* Return the minimum number of minutes that must elapse until no cell has a fresh orange.
* If this is impossible, return -1.
*
* Example 1:
*
* Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
* Output: 4
*/
See solutions to the problem at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/frequent/medium/RottingOranges.java
Observation: We are given a matrix of coordinates containing oranges some of which are rotten. Rotten oranges spread to each of the surround 4 cells per iteration. Question is asking us to find minimum number of iterations until all oranges have been rotten. We can add fresh cells in a set and add rotten in a queue. Until queue is empty, we can take a rotten cell out of the queue and mark the adjacent cells as rotten while taking a fresh cell that just rotted out of the set of fresh cells. Once the queue is empty, we can check if any fresh cells remain, if they do, we were not successful in rotting all cells. If no fresh cells remain, then we can return the number of iterations it took to process items off of the queue as minutes elapsed to rot all oranges.
Here is the code:
int [][] moves = { {1,0}, {0,1}, {-1,0}, {0,-1} };
public int orangesRotting(int[][] grid) {
Set<Pair<Integer, Integer>> visited = new HashSet<>();
Set<Pair<Integer, Integer>> fresh = new HashSet<>();
LinkedList<Pair<Integer, Integer>> queue = new LinkedList<>();
int rows = grid.length;
int cols = grid[0].length;
for (int i =0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) {
fresh.add(new Pair<>(i, j));
} else if (grid[i][j] == 2) {
queue.add(new Pair<>(i, j));
}
}
}
int loops = 0;
while (!queue.isEmpty()) {
boolean looped = false;
int size = queue.size();
for (int i =0; i < size; i++) {
Pair<Integer, Integer> point = queue.poll();
for (int[] move : moves) {
int newX = point.first + move[0];
int newY = point.second + move[1];
if (newX >= rows || newX < 0 || newY < 0 || newY >= cols) {
continue;
}
Pair<Integer, Integer> p = new Pair<>(newX, newY);
if (!visited.contains(p) && grid[newX][newY] == 1) {
if (!looped) {
loops++;
looped = true;
}
fresh.remove(p);
visited.add(p);
queue.add(p);
}
}
}
}
//if any fresh oranges left return -1
if (!fresh.isEmpty()) {
return -1;
}
return loops;
}