Rotting Oranges

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.

Example 1:

1
2
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

1
2
3
Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation:  The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

1
2
3
Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Solution:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Orange> currQueue = new LinkedList<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    currQueue.add(new Orange(i, j));
                }
            }
        }

        Queue<Orange> nextQueue = new LinkedList<>();

        int minutes = 0;

        while (!currQueue.isEmpty()) {
            while (!currQueue.isEmpty()) {
                Orange rotten = currQueue.remove();
                // top
                if (rotten.row > 0 && 
                    grid[rotten.row - 1][rotten.col] == 1) {
                    grid[rotten.row - 1][rotten.col] = 2;
                    Orange orange = new Orange(rotten.row - 1, rotten.col);
                    nextQueue.add(orange);
                }

                // bottom
                if (rotten.row < grid.length - 1 && 
                    grid[rotten.row + 1][rotten.col] == 1) {
                    grid[rotten.row + 1][rotten.col] = 2;
                    nextQueue.add(new Orange(rotten.row + 1, rotten.col));
                }

                // left
                if (rotten.col > 0 && grid[rotten.row][rotten.col - 1] == 1) {
                    grid[rotten.row][rotten.col - 1] = 2;
                    nextQueue.add(new Orange(rotten.row, rotten.col - 1));
                }

                // right
                if (rotten.col < grid[0].length - 1 && 
                    grid[rotten.row][rotten.col + 1] == 1) {
                    grid[rotten.row][rotten.col + 1] = 2;
                    nextQueue.add(new Orange(rotten.row, rotten.col + 1));
                }
            }
            
            
            if (!nextQueue.isEmpty()) {
                minutes++;
            }

            currQueue.addAll(nextQueue);
            nextQueue.clear();
        }
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) return -1;
            }
        }


        return minutes;
    }

    class Orange {
        Orange(int row, int col) {
            this.row = row;
            this.col = col;
        }

        int row;
        int col;
    }
}