Rotting Oranges

Thought Process

The problem involves simulating the rotting process of oranges in a grid. We use a Breadth-First Search (BFS) approach to propagate the rotting effect from initially rotten oranges to adjacent fresh oranges. First, we identify all initially rotten oranges and add their positions to a queue. We also count the number of fresh oranges to determine if all oranges can be rotten.

During the BFS traversal, we process each level of the queue, representing one minute of time. For each rotten orange, we check its four neighbors. If a neighbor is a fresh orange, we rot it and add it to the queue. After the BFS completes, we check if any fresh oranges remain. If so, it means not all oranges can be rotten, and we return '-1'. Otherwise, we return the total time taken.

class Solution {
    public int orangesRotting(int[][] grid) {
        
        int rows = grid.length;
        int cols = grid[0].length;
        boolean freshOrangeExist = false;

        // Add all rotten oranges in the queue
        Queue<int[]> qu = new LinkedList<>();
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){

                if(grid[i][j]==2){
                    qu.offer(new int[]{i,j});
                }

                if(grid[i][j]==1)
                    freshOrangeExist = true;
            }
        }

        // For iterating in all 4 directions
        int[] xDir = {1,-1,0,0};
        int[] yDir = {0,0,1,-1};

        int minutes = 0;
        while(!qu.isEmpty()){

            int sz = qu.size();
            for(int i=0;i<sz;i++){

                int[] arr = qu.poll();
                int x = arr[0];
                int y = arr[1];

                for(int j=0;j<4;j++){

                    int x1 = x + xDir[j];
                    int y1 = y + yDir[j];

                    // If oranges is fresh, then rote it and add it to queue
                    if(x1>=0 && x1<rows && y1>=0 && y1<cols && grid[x1][y1]==1){
                        grid[x1][y1] = 2;
                        qu.offer(new int[]{x1,y1});
                    }
                }
            }
            minutes++;
        }
        
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){

                if(grid[i][j]==1)
                    return -1;
            }
        }

        // If no freshOrange exist in the grid, then ans would be 0
        if(!freshOrangeExist)
            return 0;
        
        // Note: In last iteration all the organes are already rotten & they whould try to rotte
        // other oranges but didn't find any.
        return minutes-1;
    }
}

Code Complexity

Time Complexity: O(n * m)

The algorithm processes each cell in the grid at most once, where 'n' is the number of rows and 'm' is the number of columns.

Space Complexity: O(n * m)

The queue can store up to n * m cells in the worst case, where 'n' is the number of rows and 'm' is the number of columns.

Java: Rotting Oranges

Thought Process

Code Complexity

Time Complexity: O(n * m)

Space Complexity: O(n * m)