Rotting Oranges medium

Problem Statement

You are given an m x n grid representing a matrix where each cell can have one of three values:

• 0 representing an empty cell
• 1 representing a fresh orange
• 2 representing a rotten orange

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1

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

Example 2

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

Steps

1. Initialization: Create a queue to store the coordinates of initially rotten oranges. Also, create a variable to count the total number of fresh oranges.
2. Breadth-First Search (BFS): Perform a BFS traversal. In each iteration:
   • Get the number of rotten oranges in the current level.
   • Process each rotten orange: Explore its adjacent cells. If a fresh orange is found, mark it as rotten (change its value to 2), add its coordinates to the queue, and decrement the count of fresh oranges.
   • Increment the time counter (minutes).
3. Termination: The BFS continues until the queue is empty (no more rotten oranges to spread to). If the count of fresh oranges is zero, it means all fresh oranges have rotted. Otherwise, it means some fresh oranges remain unrotten, and we return -1.

Explanation

The problem essentially asks for the shortest time to rot all oranges using a Breadth-First Search (BFS) approach. BFS ensures we find the minimum number of minutes because it explores the grid level by level. We start with the initial rotten oranges and iteratively spread the rot to adjacent fresh oranges. The time taken is directly proportional to the number of levels (minutes) in the BFS traversal. If we ever complete the BFS and still have fresh oranges left, it's impossible to rot all of them.

Code

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int orangesRotting(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    queue<pair<int, int>> q;
    int freshOranges = 0;

    // Initialize queue and count fresh oranges
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 2) {
                q.push({i, j});
            } else if (grid[i][j] == 1) {
                freshOranges++;
            }
        }
    }

    int minutes = 0;
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};

    while (!q.empty()) {
        int rottenCount = q.size();
        for (int i = 0; i < rottenCount; ++i) {
            pair<int, int> curr = q.front();
            q.pop();
            for (int j = 0; j < 4; ++j) {
                int x = curr.first + dx[j];
                int y = curr.second + dy[j];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                    grid[x][y] = 2;
                    freshOranges--;
                    q.push({x, y});
                }
            }
        }
        if (!q.empty()) minutes++;
    }

    return freshOranges == 0 ? minutes : -1;
}

int main() {
    vector<vector<int>> grid1 = {{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};
    cout << "Minutes to rot oranges (Example 1): " << orangesRotting(grid1) << endl; // Output: 4

    vector<vector<int>> grid2 = {{2, 1, 1}, {0, 1, 1}, {1, 0, 1}};
    cout << "Minutes to rot oranges (Example 2): " << orangesRotting(grid2) << endl; // Output: -1

    return 0;
}

Complexity

• Time Complexity: O(M * N), where M and N are the dimensions of the grid. We visit each cell at most once during BFS.
• Space Complexity: O(M * N) in the worst case, where the queue might hold all the cells if the grid is densely packed with oranges.