Do you think IIT Guwahati certified course can help you in your career?
Introduction
Let’s first understand what Rotting Orange's problem is and then we’ll learn to derive an algorithm to code this in C++.
There is an n*m matrix, the cells of which contain three numbers 0, 1, or 2.
Here, 0 represents that no orange is there at that place in the matrix, 1 illustrates that a fresh orange is present at that cell in the matrix, and 2 represents that a rotten orange is present at that place in the matrix.
If a rotten orange is kept adjacent to a fresh orange, then it takes a single time frame (let’s say 1 second) for the fresh orange to rot. Given that there can only be four adjacent places top, left, bottom and right.
We have to determine the minimum number of time frames (or minimum seconds) that will take all fresh oranges to rot.
Note: If it is not possible to rot all fresh oranges, we have to return -1.
Example:
2
1
1
1
1
0
0
1
1
For the given matrix we can see that there is one rotten orange in the matrix at (0,0) and six fresh oranges at places (0,1), (0,2), (1,0), (1,1), (2,1), (2,2).
In the first time frame (1st second), the rotten orange will rot the fresh oranges kept at places (0,1) and (1,0).
2
2
1
2
1
0
0
1
1
In the 2nd second, the oranges kept at places (1,1) and (0,2) will rot.
2
2
2
2
2
0
0
1
1
In the 3rd second, the oranges kept at the place (2,1) will rot.
2
2
2
2
2
0
0
2
1
And finally, in the 4th second, the oranges kept at the place (2,2) will rot.
2
2
2
2
2
0
0
2
2
Caption: Rotting Oranges at different time frames
Picture Credits: Leet Code
So, here it took us a total of 4 seconds to rot all fresh oranges in the matrix.
In this blog post, I’ll discuss two approaches to solve this problem.
Approach 1: Brute Force Approach
The Brute force approach to solving this problem is pretty straightforward, but we’ll have to consider some things. Let’s see the algorithm to understand more.
Algorithm
We can implement this either recursively or iteratively. Here I’ll be discussing the iterative approach for the Rotting Oranges problem.
The idea here is that we’ll be traversing the complete matrix. In the matrix, if we find a rotten orange, we’ll mark its adjacent fresh oranges (if any) as rotten, and lastly, we’ll return the number of traversals it took for rotting oranges (which will be the time frames).
Firstly, we’ll initialize a variable ‘rottO’ with the value 2, because initially the rotten oranges are represented as 2.
And we’ll also keep a boolean variable to determine whether we found a rotten orange during the traversal or not.
Run the while loop.
We’ll traverse through the array, and if a fresh orange is found adjacent to the rotten orange, we’ll mark it as rottO+1.
The motive here is to distinguish the rotten oranges based on the number of matrix traversals. So the initial rotten oranges will be shown by 2 because it is the 0th traversal. The fresh oranges that rot after 1st traversal will be shown by 3, and the fresh oranges that rot after 2nd matrix traversal will be shown by 4, and so on.
If c is false, no rotten oranges are found during the traversal, so we break out of the while loop.
We’ll then check in the matrix if fresh oranges are there, we’ll return -1, or else no fresh oranges are there in the matrix, we’ll return the number of matrix traversals (which will be rottO-2).
Code
#include<bits/stdc++.h>
using namespace std;
// Check if the cell is in matrix limits
bool validMove(int x, int y, int R, int C){
return (x<R && x>=0 && y<C && y>=0);
}
// Function to find out the minimum time required for rotting oranges
int orangesRotting(int **arr, int n, int m){
// The rotten orange in the first traversal will be represented as 2
int rottO = 2;
// c represents if a rotten orange is found in a particular traversal or not
bool c = false;
while(true){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(arr[i][j]==rottO){
if(validMove(i+1, j, n, m) && arr[i+1][j]==1){
arr[i+1][j] = arr[i][j]+1;
c=true;
}
if(validMove(i, j+1, n, m) && arr[i][j+1]==1){
arr[i][j+1] = arr[i][j]+1;
c=true;
}
if(validMove(i-1, j, n, m) && arr[i-1][j]==1){
arr[i-1][j] = arr[i][j]+1;
c=true;
}
if(validMove(i, j-1, n, m) && arr[i][j-1]==1){
arr[i][j-1] = arr[i][j]+1;
c=true;
}
}
}
}
// If we didn't find a rotten orange in a traversal
if(!c) break;
c=false;
// Incrementing rottO to distinguish the rotten oranges based on the number of traversals
rottO++;
}
// If there is still fresh oranges in the matrix return -1
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(arr[i][j]==1) return -1;
// Return the number of array traversal (time frames)
return rottO-2;
}
int main(){
int n, m;
cin>>n>>m;
int **arr = new int*[n];
// Taking matrix as input
for(int i=0; i<n; i++){
arr[i] = new int[m];
for(int j=0; j<m; j++){
cin>>arr[i][j];
}
}
int ans = orangesRotting(arr, n, m);
if(ans!=-1) cout<<"The minimum time required to rot all fresh oranges is "<<ans<<" seconds.";
else cout<<"Impossible to rot all fresh oranges.";
return 0;
}
You can also try this code with Online C++ Compiler
We’ve seen a simpler brute force approach to solve this problem. But the problem with that approach is the high time complexity.
Now, Let’s learn a very efficient approach by using the Breadth-First Search technique.
In the Breadth-First search technique, we first explore a particular node’s neighbors before moving to the next node. We can say that this problem is a good use case for the BFS technique.
The main idea here is that during a single time frame, we’ll identify all the rotten oranges in the matrix and rot their adjacent fresh oranges (if any). We can keep track of the time frames by using a queue. At a particular time frame, only the new rotten oranges will be there in the queue.
Dry Run:
2
1
1
1
1
0
0
1
1
Let’s consider the given matrix,
At time frame -1, the queue will be empty.
At time frame 0, the queue will have a single orange (0,0)
At time frame 1, the queue will have two oranges (0,1) and (1,0)
At time frame 2, the queue will have two oranges (0,2) and (1,1)
At time frame 3, the queue will have one orange (2,1)
At time frame 4, the queue will have one orange (2,2).
After popping the last rotten orange, the queue will be empty, and here there are no fresh oranges left in the matrix, so we return the time frames.
Algorithm
Initialize a variable with zero, which will store the number of Fresh Oranges in the matrix.
Initialize a queue to store the coordinates of the rotten oranges at a particular time frame.
Start the while loop.
Initially, our queue will contain the coordinates of rotten oranges at time frame 0.
Just like the BFS traversal, we’ll first take the front element of the queue and rot its adjacent fresh oranges and push them in the queue.
After the 1st iteration of the while loop, we’ll have new coordinates of rotten oranges in the queue that were fresh at time frame 0.
We’ll increase the time frame and repeat the process until the queue is empty.
We’ll check if the number of fresh oranges in the matrix is not zero, then we’ll return -1 because we couldn’t make all fresh oranges rot.
If it’s zero, we’ll return the number of time frames.
Code
#include<bits/stdc++.h>
using namespace std;
// Check if the cell is in matrix limits
bool validMove(int x, int y, int R, int C){
return (x<R && x>=0 && y<C && y>=0);
}
// Function to find out minimum time required for rotting oranges
int orangesRotting(int **arr, int n, int m){
int freshO = 0;
queue<pair<int, int>> q;
// Pushing the coordinates of rotten oranges in the queue
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(arr[i][j]==2){
q.push(make_pair(i, j));
}
if(arr[i][j]==1) freshO++;
}
}
// Terminal cases where there are no fresh oranges or no rotten oranges in matrix
if(freshO==0) return 0;
if(q.empty()) return -1;
int timeFrames=-1;
// BFS Traversal through the matrix
while(!q.empty()){
int s = q.size();
for(int i=0; i<s; i++){
pair<int, int> front = q.front();
q.pop();
int cx = front.first;
int cy = front.second;
// Checking if there is an adjacent fresh orange to our current cell
if(validMove(cx+1, cy, n, m) && arr[cx+1][cy]==1){
freshO--;
arr[cx+1][cy]=2;
q.push(make_pair(cx+1, cy));
}if(validMove(cx, cy+1, n, m) && arr[cx][cy+1]==1){
freshO--;
arr[cx][cy+1]=2;
q.push(make_pair(cx, cy+1));
}if(validMove(cx-1, cy, n, m) && arr[cx-1][cy]==1){
freshO--;
arr[cx-1][cy]=2;
q.push(make_pair(cx-1, cy));
}if(validMove(cx, cy-1, n, m) && arr[cx][cy-1]==1){
freshO--;
arr[cx][cy-1]=2;
q.push(make_pair(cx, cy-1));
}
}
// Increase the time frame
timeFrames++;
}
// If there are still fresh oranges in the matrix
if(freshO!=0) return -1;
return timeFrames;
}
int main(){
int n, m;
cin>>n>>m;
int **arr = new int*[n];
// Taking matrix as input
for(int i=0; i<n; i++){
arr[i] = new int[m];
for(int j=0; j<m; j++){
cin>>arr[i][j];
}
}
int ans = orangesRotting(arr, n, m);
if(ans!=-1) cout<<"The minimum time required to rot all fresh oranges is "<<ans<<" seconds.";
else cout<<"Impossible to rot all fresh oranges.";
return 0;
}
You can also try this code with Online C++ Compiler
The minimum time required to rot all fresh oranges is 2 seconds.
Sample Input 2
3 5
2 1 0 2 1
1 0 1 0 1
1 0 0 2 1
Sample Output 2
Impossible to rot all fresh oranges.
Time Complexity
The time complexity of the BFS approach for the Rotting Oranges problem is O(n*m) because we are traversing the matrix once to store all the rotten oranges in the queue.
Space Complexity
The space complexity here would be O(n*m) because we are using a queue to store all the rotten oranges and in the worst case the all the oranges in the queue could be rotten so we’ll need n*m space to store them.
Frequently Asked Questions
What is the Rotting Oranges problem?
In the rotting oranges problem, we are given a matrix consisting of three numbers 0, 1, and 2.
Here 0, 1, and 2 represent no orange, fresh orange, and rotten orange, respectively.
A rotten orange can rot its adjacent fresh orange in a single time frame. We’ve to determine the minimum time frames required to rot all the fresh oranges.
2. What is the time complexity to solve the rotting oranges problem with Brute Force?
The time complexity for rotting oranges with the Brute Force approach is O((n*m)2).
3. What is BFS Traversal?
In BFS traversals, we first explore all the adjacent nodes of the node before proceeding on to the next node in the graph. In other words, we explore all nodes at a particular depth first before going deeper into the graph.
4. What is the time complexity and space complexity to solve the rotting oranges problem with BFS?
The time complexity is O(n*m), and space complexity is also O(n*m), where n is the number of rows and m is the number of columns in the matrix.
5. Generally, which data structure is used to implement the Breadth-First Search algorithm?
The queue data structure is used to implement the BFS algorithm.
Key Takeaways
The Rotting Oranges problem is a medium-level problem, and it’s pretty important because being an application of BFS traversal, it gets asked in the interviews of companies like Amazon.
In this blog, we discussed this problem in-depth and looked at the approaches to solve this problem.
In the interviews, always try to explain the Brute Force solution first and then come up with an efficient approach. In this problem, the BFS approach very prominently reduced the time complexity from O((n*m)2) to O(n*m).
85+ registered