C++: 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(vector<vector<int>>& grid) {

        int row = grid.size();
        int col = grid[0].size();
        int freshOrangeExist = 0;
        queue<pair<int,int>> qu;
        int minutes = 0;

        // Add rotten oranges into the queue.
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==2)
                    qu.push(make_pair(i,j));
                
                if(grid[i][j]==1)
                    freshOrangeExist = 1;
            }
        }

        // Iterating in all 4 directions
        int xDir[4] = {1,-1,0,0};
        int yDir[4] = {0,0,1,-1};
        while(!qu.empty()){

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

                pair<int,int> p1 = qu.front();  qu.pop();
                int x = p1.first;
                int y = p1.second;

                // If oranges is fresh, then rot it and add it to queue
                for(int j=0;j<4;j++){
                
                    int x1 = x + xDir[j];
                    int y1 = y + yDir[j];

                    if(x1>=row || y1>=col || x1<0 || y1<0 || grid[x1][y1]==0 || grid[x1][y1]==2)
                        continue;
                    else{
                        grid[x1][y1] = 2;
                        qu.push(make_pair(x1,y1));
                    }
                }
            }
            minutes++; 
        }
        if(freshOrangeExist==0)
            return 0;

        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==1)
                    return -1;
            }
        }
        // Bec. in last iteration all the oranges are already rotten & they would try to rot
        // 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.

Code copied!