5. 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

Example 2:

Input: grid = [[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:

Input: grid = 0,2
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 10
• grid[i][j] is 0, 1, or 2.

Approach

• We will have a queue that will have all the rotten col and row then also maintain the fresh count
• Now we go through rotten col and row then expand in all 4 to check if there any fresh that we can turn bad if yes then reduce one from fresh list and add this to rotten queue
• If we turned at least one then add to the minutes at then end
• the for loop in while we can think as first we go through the queue then by the time we are done we must have added new then we go through the list again and keep doing that till we finish
• Time: O(m*n), Space: O(m*n)

class Solution {
    public int orangesRotting(int[][] grid) {
        int row = grid.length, col = grid[0].length;
        //check all directions around
        int[][] directions = new int[][]{{0,1},{1,0},{-1,0},{0,-1}};
        Queue<int[]> rot = new LinkedList<>();
        
        int fresh = 0; //first we collect all fresh then by the end it should reach 0
        for (int i = 0; i < row; i++) {
            for (int j= 0; j < col; j++) {
                if (grid[i][j] == 2) {
                    rot.offer(new int[]{i,j}); // rotten col and row
                } else if (grid[i][j] == 1) {
                    fresh++; // fresh count
                }
            }
        }
        //all the oranges are rotten from the start
        if (fresh == 0)
            return 0;
        //for the answer
        int minutes = 0;
        while (!rot.isEmpty()) {
            boolean rotted = false; //if in all 4 there is any fresh then turn rotted and add minutes
            for (int i = rot.size(); i > 0; i--) {
                int[] ora = rot.poll();
                for(int[] dir: directions) {
                    int r = ora[0] + dir[0];
                    int c = ora[1] + dir[1];
                    if (r >= 0 && r < row && c >= 0 && c < col && grid[r][c] == 1) {
                        grid[r][c] = 2; //turn rotten
                        rot.offer(new int[]{r,c}); //add newly rotten in the queue
                        fresh--; //now rotted
                        rotted = true; //we have turned atleast one rotten
                    }
                }
            }
            if (rotted) //since we turn rotted we need to add minute
                minutes++;
        }
 
        return (fresh == 0) ? minutes : -1;
    }
}