Interactive Programming Education Platform

Logic Practice

Introduction

The Problem of Decayed Oranges is a classic challenge in algorithmics that evaluates our understanding of graph traversal algorithms, particularly Breadth-First Search. This problem is a common feature in interviews and covers topics such as multi-source BFS and resolving grid-based issues.

This guide will address the issue by initially detailing the approach to solving it, followed by a comprehensive breakdown of the step-by-step implementation in C++.

Problem Statement

We have an array grid containing integers in a two-dimensional structure. Each cell in the grid can be classified into one of three categories: 0 for an empty cell, 1 for a fresh orange, and 2 for a rotten orange.

A ripe orange will spoil over time if it is next to at least one spoiled orange vertically or horizontally. The goal is to calculate the shortest duration required to spoil all the fresh oranges on the grid. If it is not feasible to spoil all fresh oranges, the function should return -1.

Constraints:

✅ The dimension of the grid are m x n.
✅ The value of each cell is in the range of 0 to 2.

Approach:

Multi-source breadth-first search is a good approach for this problem due to the fact that the process of rotting spreads as a result of multiple sources (the rotten oranges) at once. Here is a breakdown of how it works:

✅ Set up a grid and keep a look for all the rotten orange coordinates and enqueue them.
✅ In a similar fashion, go ahead with BFS while using the queue to rot the remaining adjacent oranges, for every orange rotted, decrease the fresh orange count.
✅ Return the time taken for all the freshly rotted oranges along with the -1 value in case some fresh oranges are left untouched.

Example 1:

Let's consider a scenario to demonstrate the Rotten Oranges Issue in C++.

Example


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

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

    // Step 1: Add all rotten oranges to the queue and count fresh oranges
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 2) {
                q.push({i, j});
            } else if (grid[i][j] == 1) {
                freshOranges++;
            }
        }
    }

    // Step 2: Perform BFS
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    while (!q.empty() && freshOranges > 0) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front();
            q.pop();

            for (auto [dx, dy] : directions) {
                int nx = x + dx;
                int ny = y + dy;

                // Check bounds and if the orange is fresh
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2; // Rot the orange
                    q.push({nx, ny});
                    freshOranges--; // Decrease fresh orange count
                }
            }
        }
        time++;
    }

    // Step 3: Return result
    return freshOranges == 0 ? time : -1;
}

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

    int result = orangesRotting(grid);
    if (result != -1) {
        cout << "Minimum time required to rot all oranges: " << result << endl;
    } else {
        cout << "Not all oranges can rot." << endl;
    }

    return 0;
}

Output:

Output


Minimum time required to rot all oranges: 4

Explanation of the Code:

✅ Input Traversal: During the first traversing of the grid, the rotting and the fresh oranges are identified and their locations are marked.
✅ BFS Loop: Every time the BFS loop is executed, a level of the queue, which represents one unit of time, is processed.
✅ Boundary and Fresh Check: Before rotting an orange, the code makes sure that the cell is within bounds and contains a fresh orange.
✅ Result: The entire time zone will be returned if there are no fresh oranges remaining, otherwise a value of -1 is returned.

Time and Space Complexity

✅ Time Complexity: O(m×n) m and n are the dimensions of the grid. Every cell is processed independently, that is once.
✅ Space Complexity: O(m×n) refers to the space occupied by the queue in the BFS algorithm.

Example 2:

Let's consider another instance to demonstrate the Rotten Oranges Issue in C++.

Example


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

// Function to validate the grid
void validateGrid(const vector<vector<int>>& grid) {
    if (grid.empty()) {
        throw invalid_argument("Grid cannot be empty.");
    }
    for (const auto& row : grid) {
        if (row.empty()) {
            throw invalid_argument("Each row in the grid must contain at least one element.");
        }
        for (int cell : row) {
            if (cell < 0 || cell > 2) {
                throw invalid_argument("Grid can only contain values 0, 1, or 2.");
            }
        }
    }
}

// Helper function to print the grid (for debugging purposes)
void printGrid(const vector<vector<int>>& grid) {
    for (const auto& row : grid) {
        for (int cell : row) {
            cout << cell << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// BFS function to calculate the minimum time to rot all oranges
int minimumTimeToRot(vector<vector<int>>& grid) {
    validateGrid(grid);  // Ensure the grid is valid

    int rows = grid.size();
    int cols = grid[0].size();
    queue<pair<int, int>> q;
    int freshCount = 0;
    int time = 0;

    // Directions for traversing the grid (up, down, left, right)
    vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    // Step 1: Identify initial rotten oranges and count fresh ones
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 2) {
                q.push({i, j});
            } else if (grid[i][j] == 1) {
                freshCount++;
            }
        }
    }

    // If there are no fresh oranges, return 0 immediately
    if (freshCount == 0) {
        return 0;
    }

    // Step 2: Perform BFS
    while (!q.empty()) {
        int size = q.size();
        bool anyRotting = false; // Track if any fresh orange rotted in this step

        for (int i = 0; i < size; i++) {
            auto [x, y] = q.front();
            q.pop();

            for (auto [dx, dy] : directions) {
                int nx = x + dx;
                int ny = y + dy;

                // Check if the neighbor is valid and fresh
                if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 1) {
                    grid[nx][ny] = 2;  // Rot the fresh orange
                    q.push({nx, ny});
                    freshCount--;  // Decrease fresh orange count
                    anyRotting = true;
                }
            }
        }

        if (anyRotting) {
            time++;  // Increment time only if a fresh orange rotted
        }
    }

    // Step 3: Check if all fresh oranges are rotted
    return freshCount == 0 ? time : -1;
}

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

        cout << "Input Grid:" << endl;
        printGrid(grid);

        // Calculate minimum time
        int result = minimumTimeToRot(grid);

        // Print the result
        if (result != -1) {
            cout << "Minimum time required to rot all oranges: " << result << endl;
        } else {
            cout << "Not all oranges can rot." << endl;
        }

        cout << "Final Grid State:" << endl;
        printGrid(grid); // Print the final state of the grid

    } catch (const exception& e) {
        cerr << "Error: " << e.what() << endl;
    }

    return 0;
}

Output:

Output


Input Grid:
2 1 1 0 
1 1 0 2 
0 1 1 1 
2 0 0 1 

Minimum time required to rot all oranges: 4

Final Grid State:
2 2 2 0 
2 2 0 2 
0 2 2 2 
2 0 0 2

Explanation:

✅ validateGrid: This process is important because it makes certain that the grid is valid (not empty, only 0, 1, 2). Invalid grids throw errors.
✅ printGrid: It is used for debugging or visualization by printing the grid.
✅ minimumTimeToRot: Initialization: It counts fresh oranges while enqueuing all rotten ones. BFS Traversal: Rotting is spread in all four directions (which is why there is a queue). Time is kept for every step and whenever a fresh orange is eaten, it is decremented. Result: The total time is returned if all are rotten. If there is a fresh orange remaining, -1 is returned.
✅ main: Set up the input grid, validate it, calculate the result and print the initial/final state of the grid along with the output.
✅ Initialization: It counts fresh oranges while enqueuing all rotten ones.
✅ BFS Traversal: Rotting is spread in all four directions (which is why there is a queue). Time is kept for every step and whenever a fresh orange is eaten, it is decremented.
✅ Result: The total time is returned if all are rotten. If there is a fresh orange remaining, -1 is returned.

Complexity Analysis:

✅ Time Complexity: O(m×n)
✅ Space Complexity: O(m×n) for the queue used in BFS.

Takeaway Points:

✅ Multi-Source BFS Explained: Here, we can see multi-source BFS in action, where all sources (rotten oranges) are actively spreading at once.
✅ Grid Traversal Techniques: It demonstrates how to traverse two-dimensional grids using efficient direction vectors (up, down, left, right).
✅ Edge Case Handling: Grids that have no fresh oranges (output 0). Fresh oranges that can only be isolated and do not rot (output -1). Empty grids or grids that have no valid inputs.
✅ BFS Queue: It ensures that all nodes (oranges) at the same "time level" are processed before splitting off to the next.
✅ Practical Use Cases: Models' real-life problems like the spread of disease, fire spread simulation, and even diffusion of resources.
✅ Grids that have no fresh oranges (output 0).
✅ Fresh oranges that can only be isolated and do not rot (output -1).
✅ Empty grids or grids that have no valid inputs.

Conclusion:

In summary, the Rotten Oranges Challenge serves as an ideal exercise for honing BFS skills and tackling spatial grid dilemmas. It showcases the application of multi-source BFS strategy and enables the correlation of real-world situations with graph traversal concepts.

Rotten Oranges Problem In C++