Rotten Oranges Problem

Introduction

• Problem Statement: Given a grid of dimensions n x m where:
  • 0: Empty cell
  • 1: Fresh orange
  • 2: Rotten orange
• Objective: Determine the minimum time required to rot all oranges.
• Rotting Mechanism: Rotten oranges rot adjacent fresh oranges (up, down, left, right) in 1 unit of time.

Problem Breakdown

• Example 1:
  • Initial State: 2D grid with mixed fresh and rotten oranges.
  • Time 1 Unit: Rotten oranges rot adjacent fresh oranges.
  • Continue until all reachable fresh oranges are rotten or no fresh oranges left.
  • Result: Time taken to rot all fresh oranges or -1 if some fresh oranges can't be reached.
• Example 2:
  • Multiple initially rotten oranges rot adjacent oranges in 1 unit of time.
  • Check if all fresh oranges are rotten.
• Example 3:
  • Single rotten orange in the grid.
  • Follow similar rotting process as above.
  • Return minimum time to rot or -1 if any orange is unreachable.

Important Observations

• A rotten orange can only rot adjacent oranges (no diagonal rotting).
• If some oranges cannot be rotted (isolated by empty cells), return -1.

Algorithm Choice: BFS (Breadth-First Search)

• Reason: BFS processes nodes level-wise, ensuring minimum time traversal for rotting.
• Why Not DFS: DFS would take more steps/time as it goes deep into one branch before visiting others.
• BFS Steps:
  • Use a queue to traverse level by level.
  • Initially, enqueue all rotten oranges with time 0.
  • For each rotten orange, enqueue its adjacent fresh oranges with incremented time.
  • Track the maximum time during the process.

BFS Implementation

1. Initialization:
   • Determine grid dimensions n and m.
   • Create a queue to store rotten oranges and their rotting times.
   • Create a visited array to mark rotten cells.
2. Enqueue Initial Rottens:
   • Traverse grid and enqueue all initially rotten oranges with time 0.
   • Mark these as visited.
3. BFS Traversal:
   • Dequeue elements and check their adjacent cells.
   • Enqueue fresh oranges and update their rotting times.
   • Mark these new rotten oranges as visited.
4. Final Checks:
   • Ensure all fresh oranges are rotten by checking the visited array.
   • Return the total rotting time or -1 if any fresh orange is left.

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

void rottenOranges(vector<vector<int>>& grid) {
    int n = grid.size();
    int m = grid[0].size();
    queue<pair<pair<int, int>, int>> q; // store cell position and time
    vector<vector<int>> visited(n, vector<int>(m, 0));
    int freshCount = 0; // fresh oranges count
    
    // Enqueue initial rotten oranges
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (grid[i][j] == 2) {
                q.push({{i, j}, 0});
                visited[i][j] = 1;
            } else if (grid[i][j] == 1) {
                ++freshCount;
            }
        }
    }

    // Direction vectors for top, right, bottom, left
    vector<int> dRow = {-1, 0, 1, 0};
    vector<int> dCol = {0, 1, 0, -1};
    int time = 0;

    // BFS traversal
    while (!q.empty()) {
        auto cell = q.front(); q.pop();
        int row = cell.first.first;
        int col = cell.first.second;
        int t = cell.second;
        
        // Update the final time
        time = max(time, t);

        // Check all 4 possible neighbors
        for (int i = 0; i < 4; ++i) {
            int newRow = row + dRow[i];
            int newCol = col + dCol[i];
            
            // Check for valid cell and fresh orange
            if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m && 
                grid[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                q.push({{newRow, newCol}, t + 1});
                visited[newRow][newCol] = 1;
                --freshCount;
            }
        }
    }

    // If there are still fresh oranges left
    if (freshCount > 0) {
        cout << "-1" << endl;
    } else {
        cout << time << endl;
    }
}

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

Complexity Analysis

• Space Complexity: O(n * m) (queue and visited arrays).
• Time Complexity: O(n * m) traversing each cell and its 4 neighbors.

Conclusion

• Use BFS for minimum time traversal in grid problems involving equal level processing.
• Ensure all fresh oranges are processed, otherwise return -1.