Graph: Find minimum time to rot all the oranges

Problem Statement:

You are given a 2D matrix, where each has 3 values.

0 represents empty cells
1 represent fresh orange
2 represent rotten orange.

If a fresh orange that is adjacent to any rotten orange, becomes rotten.

Return minimum time required so that all the oranges become rotten.

1 unit of time is taken to rotten each orange.

Example:

Input:  mat[][] = [[2, 1, 0, 2, 1], 
                    [1, 0, 1, 2, 1], 
                    [1, 0, 0, 2, 1]]
Output: 2

Solution Explanation:

Take a queue to store the rotten oranges and a variable to store the count of the number of fresh oranges.

In a loop:
Store the count of fresh oranges
Store the index of the rotten oranges

Then,

Get the front of the queue and check in all the 4 directions if there are any fresh oranges,

If there are fresh orange, then change it to rotten and decrement count of fresh oranges and increment the minutes.

At the end, check if there are any fresh orange, then return accordingly

Time Complexity: O(m*n)
Space Complexity: O(m*n)

Code Solution

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int solution(vector<vector<int>> &grid)
{
    if (grid.empty()) 
        return 0;

    int freshOrangesCount = 0;

    int m = grid.size();
    int n = grid[0].size();

    queue<pair<int, int>> q;

    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 1)
                freshOrangesCount++;
            else if (grid[i][j] == 2)
                q.push({i, j});
        }
    }

    int time = 0;
   
    vector<pair<int, int>> dirs = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

    while (freshOrangesCount != 0 && !q.empty())
    {
        int qsize = q.size();

        for (int i = 0; i < qsize; i++)
        {
            int rottenI = q.front().first;
            int rottenJ = q.front().second;
            q.pop();

            for (auto d : dirs)
            {
                int newX = rottenI + d.first;
                int newY = rottenJ + d.second;

                if (newX >= 0 && newX < m && newY >= 0 && newY < n && grid[newX][newY] == 1)
                {
                    grid[newX][newY] = 2;
                    freshOrangesCount--;
                    q.push({newX, newY});
                }
            }
        }
        time++;
    }
    return freshOrangesCount == 0 ? time : -1;
}

int main() 
{
    vector<vector<int>> mat = {{2, 1, 0, 2, 1}, {1, 0, 1, 2, 1}, {1, 0, 0, 2, 1}};
    cout << solution(mat) << endl;
    return 0;
}

Output

2