Rotten Oranges Problem

Jul 15, 2024

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.