Problem Statement:

You are given an n x m grid where:

• 2 represents a rotten orange.
• 1 represents a fresh orange.
• 0 represents an empty cell.

Every minute, a rotten orange rots all adjacent fresh oranges in the 4 directions (up, down, left, and right). Your task is to return the minimum number of minutes required so that all fresh oranges become rotten. If it is impossible for all fresh oranges to rot, return -1.

Input:

• A 2D grid of size n x m where each cell contains one of the values 0, 1, or 2.

Output:

• Return the minimum number of minutes required to rot all fresh oranges. If it is not possible, return -1.

Constraints:

• The number of rows and columns is within the range [1, 10].
• Each cell in the grid contains one of 0, 1, or 2.

Examples

Example 1:

Input: grid = [
               [2, 1, 1],
               [1, 1, 0],
               [0, 1, 1]
              ]

Output: 4

Explanation:
The rotten orange at the position (0, 0) rots all adjacent fresh oranges in 4 minutes.

Example 2:

Input: grid = [
               [2, 1, 1],
               [0, 1, 1],
               [1, 0, 1]
              ]

Output: -1

Explanation:
It is impossible to rot all fresh oranges, as there is a fresh orange that is completely isolated by empty cells.

Example 3:

Input: grid = [
               [0, 2]
              ]

Output: 0

Explanation:
There are no fresh oranges in the grid, so no time is required.

Theory:

This problem can be visualized as a multi-source Breadth-First Search (BFS) problem. Each rotten orange acts as a source, and we propagate the infection to neighboring fresh oranges. The BFS ensures that we simulate the rotting process minute by minute, level by level.

The key idea is to:

1. Start BFS from all rotten oranges (all sources at time 0).
2. For each rotten orange, propagate the infection to neighboring fresh oranges.
3. Continue until no fresh oranges remain or no more oranges can be rotted.

Different Approaches

1️⃣ BFS (Breadth-First Search)

Intuition:

The idea is that for each rotten orange, the number of fresh oranges that are there its 4 directions can be found. With the passing of every minute, these fresh oranges will be rottened which will further rotten other fresh oranges in contact.

Consider each minute as level, where all the oranges will be rotten at once. Keeping this in mind, a level order traversal (BFS) can be performed making sure at each level, the fresh oranges in contact with the already rotten oranges gets rotten.

The number of levels for which the BFS is performed will denote the time taken by all oranges to rotten.

How to identify if all the oranges are rotten or not?

For this, a count can be maintained for the oranges that gets rotten after the traversal is complete. And a total count of oranges can be found by traversing the grid.
If the total count matches with the count of rotten oranges, it can be concluded that all the oranges were rotten.

Approach:

1. Determine the dimensions of grid. Variables are initialized to track time, total number of oranges, and the count of rotten oranges. A queue is taken for BFS traversal that will store the coordinates of the rotten oranges at that current level.
2. Traverse the grid and update the count of total oranges. If any cell containing rotten orange is found, add it to the queue.
3. Perform BFS to spread Rot. Continue until the queue is empty and for each level (each minute)
   1. Record the size of the queue, which represents the number of rotten oranges at that moment. And update the count of rotten oranges by adding the size of the queue.
   2. Process each rotten orange, by removing it from the queue, marking its four fresh oranges (if any) as rotten and adding them to the queue.
   3. If new oranges are marked rotten during this process, increment the time.
4. After processing, if the count of rotten oranges matches the total number of oranges, return the time taken. If not all oranges are rotten, return -1 to indicate it's not possible to rot all oranges.

Dry Run:

Input: grid =
              0     1     2   
           +-----+-----+-----+
        0  |  2  |  1  |  1  |
           +-----+-----+-----+
        1  |  0  |  1  |  1  |
           +-----+-----+-----+
        2  |  1  |  0  |  1  |
           +-----+-----+-----+

Iterate through the grid during which find out the count of healthyOranges and push the rotten oranges into the queue

grid =        0     1     2   
           +-----+-----+-----+
        0  |  2  |  1  |  1  |
           +-----+-----+-----+
        1  |  0  |  1  |  1  |
           +-----+-----+-----+
        2  |  1  |  0  |  1  |
           +-----+-----+-----+

healthyCount = 6
timeTaken  = 0
   
   |        |
   |        |
   |        |
   |        |
   |        |
   |        |
   | (0, 0) | <- rotten tomatoes as
   +--------+    pair of (row, column)

Keep Processing the neighbors of the rotten oranges:

        0     1     2   
     +-----+-----+-----+
  0  || 2 ||  1  |  1  |
     +-----+-----+-----+
  1  |  0  |  1  |  1  |
     +-----+-----+-----+
  2  |  1  |  0  |  1  |
     +-----+-----+-----+

Keep Processing until queue is empty
    currentQueueSize = queue.size()
                     = 1
    Keep doing the below process till currentQueueSize
    is 0.
      Pop the front from the row,
      which is (0, 0)

       |        |
       |        |
       |        |
       |        | (empty queue)
       +--------+

      front = (0, 0)
      Convert the healthy orange neighbor of front
      to rotten and push them into the queue.
      The healthy neighbor of the (0, 0) are:
                   (0, 1)
                   (0, 1) = 2
                   push(0, 1) into queue
       |        |
       |        |
       |        |
       | (0,1)  |
       +--------+
    

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    // DelRow and delCol for neighbors
    vector<int> delRow = {-1, 0, 1, 0};
    vector<int> delCol = {0, 1, 0, -1};
    
    /* Helper Function to check if a 
    cell is within boundaries */
    bool isValid(int &i, int &j, 
                 int &n, int &m) {
        
        // Return false if cell is invalid
        if(i < 0 || i >= n) return false;
        if(j < 0 || j >= m) return false;
        
        // Return true if cell is valid
        return true;
    }
    
public:
    /* Function to find number of minutes 
    so that all oranges get rotten */
    int orangesRotting(vector<vector<int>> &grid){
        
        // Get the dimensions of grid
        int n = grid.size();
        int m = grid[0].size();
        
        /* Variable to store time taken
        to get all oranges rotten */
        int time = 0;
        
        /* Variable to store 
        total count of oranges */
        int total = 0;
        
        /* Variable to store count of 
         oranges that are rotten */
        int count = 0;
        
        // Queue to perform BFS
        queue<pair<int,int>> q;
        
        // Traverse the grid
        for(int i=0; i < n; i++) {
            for(int j=0; j < m; j++) {
                
                /* If cell contains orange, 
                increment total */
                if(grid[i][j] != 0) total++;
                
                /* If cell contains rotten 
                 orange, push in queue */
                if(grid[i][j] == 2) {
                    q.push({i, j});
                }
            }
        }
        
        // Perform BFS
        
        // Until the queue is empty
        while(!q.empty()) {
            
            // Get the size of queue
            int k = q.size();
            
            // Update count of rotten oranges
            count += k;
            
            // Perform BFS for current level
            while(k--) {
                
                // Get the cell from queue
                auto cell = q.front();
                q.pop();
                
                // Get its coordinates
                int row = cell.first;
                int col = cell.second;
                
                // Traverse its 4 neighbors
                for(int i=0; i < 4; i++) {
                    
                    // Coordinates of new cell
                    int nRow = row + delRow[i]; 
                    int nCol = col + delCol[i]; 
                    
                    /* check for valid, unvisited 
                     cells having fresh oranges */
                    if(isValid(nRow, nCol, n, m) && 
                       grid[nRow][nCol] == 1) {
                        
                        /* Mark the new orange as rotten
                        and add it to the queue */
                        grid[nRow][nCol] = 2;
                        q.push({nRow, nCol});
                    }
                }
            }
            
            /* If new oranges are rotten, then
             the time must be incremented */
            if(!q.empty()) time++;
        }
        
        /* If all the oranges are rotten,
        return the time taken */
        if(total == count) return time;
        
        // Otherwise return -1
        return -1;
    }
};

int main() {
    vector<vector<int>> grid = {
        {2, 1, 1}, 
        {1, 1, 0}, 
        {0, 1, 1}
	};
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    /* Function call to find number of minutes 
    so that all oranges get rotten */
    int ans = sol.orangesRotting(grid);
    
    cout << "The minimum number of minutes required for all oranges to rotten are: " << ans;
    return 0;
}

Complexity Analysis:

• Time Complexity: O(N*M) (where N and M are the dimensions of grid)
  • In the worst case, each fresh orange in the grid will be rotten and for each rotten orange, its 4 neighbors are checked taking O(4*N*M) time.
• Space Complexity: O(N*M)
  • Using a queue data structure, which will store all cells if a grid is full of rotten oranges taking O(N*M) space.