994. Rotting Oranges | LeetCode | Java | Problem Solving

Subscribe to my newsletter and never miss my upcoming articles

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.

image.png

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.

class Solution {
    public int orangesRotting(int[][] grid) {
int noOfMinutes=0, noOfFreshFruits=0, row = grid.length, col = grid[0].length;
        if(row==0)
            return 0;
        Queue<int[]> queue = new LinkedList<>();
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                if(grid[i][j]==2){
                    queue.offer(new int[]{i,j});
                }
                else if(grid[i][j]==1){
                    noOfFreshFruits++;
                }
            }
        }
        if(noOfFreshFruits==0)
            return 0;
        int[][] axis = new int[][]{{0,-1}, { -1,0}, {1,0}, {0,1}};
        while(!queue.isEmpty()){
            noOfMinutes++;
            int size = queue.size();
            for( int i=0; i<size; i++){
                int[] position = queue.remove();
                for( int[] arr : axis){
                    int x = position[0] + arr[0];
                    int y = position[1] + arr[1];

                    if( x<0 || x>=row || y<0 || y>=col || grid[x][y]!=1){
                        continue;
                    }
                    queue.offer(new int[] {x,y});
                    grid[x][y]=2;
                    noOfFreshFruits--;
                }
            }
        }
        if(noOfFreshFruits>0)
            return -1;
        return noOfMinutes-1;    }
}
 
Share this