Rotten Oranges - GFG question

Problem Statement: Given a grid of dimension N x M where each cell in the grid can have values 0, 1, or 2 which has the following meaning:

0: Empty cell

1: Cells have fresh oranges

2: Cells have rotten oranges

We have to determine what is the minimum time required to rot all oranges. A rotten orange at index [i,j] can rot other fresh oranges at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time. 

Examples:

Example 1:

Input:

Output: 4

Solution

Disclaimer: try it out yourself first.

Intuition:

A rotten orange at index [i,j] can rot other fresh oranges at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time, i.e., in 4 directions.

The question arises of which algorithm to use.

A rotten orange can rot fresh orange neighbours that are at a distance of 1 or at the same level. It means each of them got rotten at a similar level or stage, implying we need to visit the same level at the same time. Hence, level-wise traversal is BFS traversal.

If we use DFS traversal then all neighbouring fresh oranges will be visited depth-wise. But here it is not the case to rot all the oranges, we need to find the minimum time to rot them all, which is possible only when we are in neighbouring directions at an equal pace. We want to rotten them simultaneously.

So, BFS traversal will be used to solve this problem. 

Approach:

Initial configuration:

• Queue: contains a couple of starting points that will depend on the number of rotten oranges present initially.
• Visited array: is of the same size as the grid. The visited cell represents rotten orange.

The algorithm steps are as follows:

• For BFS traversal, we need a queue data structure and a visited array. Create a replica of the given array, i.e., create another array of the same size and call it a visited array. We can use the same matrix, but we will avoid alteration of the original data. 
• The pairs of cell number and initial time, i.e., <<row, column>, time> will be pushed in the queue and marked as visited (represents rotten) in the visited array. For example, ((2,0), 0) represents cell (2, 0) and initial time 0.  
• While BFS traversal, pop out an element from the queue and travel to all its neighbours. In a graph, we store the list of neighbours in an adjacency list but here we know the neighbours are in 4 directions. 
• We go in all 4 directions and check for valid unvisited fresh orange neighbours. To travel 4 directions we will use nested loops, you can find the implementation details in the code. 
• BFS function call will make sure that it starts the BFS call from each rotten orange cell, and rotten all the valid fresh orange neighbours and puts them in the queue with an increase in time by 1 unit. Make sure to mark it as rotten in the visited array.  
• Pop-out another rotten orange from the queue and repeat the same steps until the queue becomes empty.
• Add a counter variable to store the maximum time and return it. If any of the fresh was not rotten in the visited array then return -1.

C++ Code

int orangesRotting(vector<vector<int>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        queue<vector<int>> q;
        int lvl = -1;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j]==2){
                    q.push({i, j});
                }
            }
        }
        
        vector<vector<int>> dir={{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        
        while(!q.empty()){
            int qn = q.size();
            while(qn--){
                vector temp;
                temp = q.front();
                q.pop();
                for(int i = 0; i < 4; i++){
                    int qi = temp[0]+dir[i][0];
                    int qj = temp[1]+dir[i][1];
                    if(qi >= 0 && qi < n && qj >= 0&& qj < m && grid[qi][qj]==1){
                        grid[qi][qj]=2;
                        q.push({qi, qj});
                    }   
                }
            }
            lvl++;
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1){
                    return -1;
                }
            }
        }
        return lvl == -1 ? 0 : lvl;
    }

Output: 1

Time Complexity: O(NxM + NxMx4) ~ O(N x M), For the worst case, all of the cells will have fresh oranges, so the BFS function will be called for (N x M) nodes and for every node, we are traversing for 4 neighbours, it will take O(N x M x 4) time.

Space Complexity ~ O(N x M), O(N x M) for copied input array and recursive stack space takes up N x M locations at max.