RottenOranges.cpp

#include <bits/stdc++.h>

using namespace std;

/*
Problem Statement:
Given an m x n grid, where each cell has the following values:
2  –  Rotten orange
1  –  Fresh orange
0  –  Empty cell

Every minute, if a Fresh orange is adjacent to a Rotten Orange in 4-direction
(upward, downwards, right, and left) it becomes Rotten.

Return the minimum number of minutes required such that
none of the cells has a Fresh Orange.
If it's not possible, return -1.
*/

// Approach: BFS

bool isValid(int nx, int ny, int m, int n)
{
    return (0 <= nx && nx < m) &&
           (0 <= ny && ny < n);
}

// Time: O(mn) x 4
// Space: O(mn)
int orangesRotting(vector<vector<int>> &grid)
{
    int m = grid.size();
    int n = grid[0].size();

    int total = 0; // fresh + rotten oranges
    int count = 0; // rotten oranges
    int mins = 0;  // minutes elapsed

    queue<pair<int, int>> rotten; // {i, j}: position of rotten orange

    // Count the fresh & rotten oranges, push rotten oranges into queue
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] != 0) // Rotten or Fresh orange
                total++;
            if (grid[i][j] == 2)     // Rotten
                rotten.push({i, j}); // Push position of rotten orange
        }
    }

    int dx[] = {0, 0, -1, 1}; // 4-directions (x-axis)
    int dy[] = {-1, 1, 0, 0}; // 4-directions (y-axis)

    while (!rotten.empty())
    {
        int size = rotten.size(); // rotten oranges in current minute
        count += size;            // add to total rotten oranges

        while (size--) // Each rotten orange in current minute
        {
            // Pop the front rotten orange
            int x = rotten.front().first;
            int y = rotten.front().second;
            rotten.pop();

            // Check for fresh oranges in 4-directions
            for (int i = 0; i < 4; i++)
            {
                // New coordinates
                int nx = x + dx[i];
                int ny = y + dy[i];

                // Valid, fresh orange
                if (isValid(nx, ny, m, n) && grid[nx][ny] == 1)
                {
                    grid[nx][ny] = 2;      // make it rotten
                    rotten.push({nx, ny}); // push it into queue
                }
            }
        }

        if (!rotten.empty()) // if there are more rotten oranges
            mins++;
    }

    if (total != count) // fresh oranges left
        return -1;

    return mins;
}

int main()
{
    vector<vector<int>> grid = {{2, 1, 1},
                                {1, 1, 0},
                                {0, 1, 1}};

    cout << orangesRotting(grid) << endl; // 4

    return 0;
}