Rotten Oranges

Question:

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.

Solution:

• Each rotten orange, rottens the neighboring oranges “simultaneously”.
• Simple BFS solution.

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        int freshOranges = 0, minutes = 0;
        Queue<int[]> q = new LinkedList<>();
 
        // Step 1: Count fresh oranges and add rotten oranges to the queue
        // This step helps us keep track of the initial state of the grid
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(grid[i][j] == 1){
                    freshOranges++;
                } else if(grid[i][j] == 2){
                    q.offer(new int[]{i, j, 0}); //current row, current col and current minute
                }
            }
        }
 
        // Define the directions for neighboring cells: left, right, bottom, up
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
 
        // Step 2: BFS traversal to rot fresh oranges
        while(!q.isEmpty()){
            //Remove
            int[] currCell = q.poll();
            int currRow = currCell[0];
            int currCol = currCell[1];
            int currMin = currCell[2];
 
            /*
            mark* step (can create a visited but we're handling 
            it's need by decreasing fresh oranges while adding neighbours)
            */
 
			/**
            ==work==
	            In BFS,currMin is Always Increasing: Since BFS guarantees that oranges at minute 2 are processed only after those at minute 1, 
	            and so on, currMin will naturally increase with each level of BFS.
	            Effectively capturing the current time step of the BFS traversal. Since BFS processes each level in order, 
	            currMin at the last processed orange will indeed be the total time required
            **/
            minutes = currMin;
		
            //add*
            for(int[] direction: directions){
                int newRow = currRow + direction[0];
                int newCol = currCol + direction[1];
 
                if(newRow >= 0 && newCol >= 0 &&
                   newRow < grid.length &&
                   newCol < grid[0].length &&
                   grid[newRow][newCol] == 1 //isFresh
                ){
                    grid[newRow][newCol] = 2; //rotten it
                    freshOranges--;
                    q.offer(new int[]{newRow, newCol, currMin + 1});
                }
            }
 
        }
        return freshOranges == 0 ? minutes : -1;
    }
}