Home » Interview coding problems/challenges

Rotten Oranges

Rotten Oranges: In this article, we are going to see how to solve an interview problem based on graph? This problem has been featured in Amazon, Microsoft coding rounds. Submitted by Souvik Saha, on March 26, 2019

Problem statement

Given a matrix of dimension r*c where each cell in the matrix can have values 0, 1 or 2 which has the following meaning:

• 0 : Empty cell
• 1 : Cells have fresh oranges
• 2 : Cells have rotten oranges

So, we have to determine what is the minimum time required to all oranges. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time. If it is impossible to rot every orange then simply return -1.

Example

    Input:
    2
    3 5
    2 1 0 2 1 1 0 1 2 1 1 0 0 2 1

    Output:
    2

Explanation

Algorithm

To implement this question we use BFS and a queue data structure.

1. At first, we push all positions into the queue which has 2 and make a partition by inserting NULL into the queue.
2. We pop every element from the queue until the first NULL comes and Go for its four neighbor's if there is any 1 then make it two and push it into the queue and separate this section again inserting a NULL into the queue.
3. Whenever we encounter NULL except for the first NULL and if it is not a last element of the queue then we increase the count value.
4. Repeat step 2 to 3 until the queue is empty.

C++ Implementation for Rotten Oranges problem

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

bool zero(int *arr,int r,int c){
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			if(*((arr+i*c)+j)==1)
				return false;
		}
	}
	return true;
} 

int rotten(int *arr,int r,int c){
	queue<pair<int,int> >q;
	int store=0,temp=0;
	for(int i=0;i<r;i++){
		for(int j=0;j<c;j++){
			if(*((arr+i*c)+j)==2){
				q.push(make_pair(i,j));
			}
		}
	}
	q.push(make_pair(-1,-1));
	while(!q.empty()){
		pair<int,int> p=q.front();
		q.pop();
		if(p.first!=-1){
			if(*((arr+p.first*c)+p.second)==1){
				temp=1;
				*((arr+p.first*c)+p.second)=2;
			}
			if(p.first==0 && p.second==0){
				if(*((arr+(p.first+1)*c)+p.second)==1){
					q.push(make_pair((p.first+1),p.second));
				}
				if(*((arr+(p.first)*c)+p.second+1)==1){
					q.push(make_pair((p.first),p.second+1));
				}
			}
			else if(p.first==0 && p.second==c-1){
				if(*((arr+(p.first+1)*c)+p.second)==1){
					q.push(make_pair((p.first+1),p.second));
				}
				if(*((arr+(p.first)*c)+p.second-1)==1){
					q.push(make_pair((p.first),p.second-1));
				}
			}
			else if(p.first==0){
				if(*((arr+(p.first+1)*c)+p.second)==1){
					q.push(make_pair((p.first+1),p.second));
				}
				if(*((arr+(p.first)*c)+p.second-1)==1){
					q.push(make_pair((p.first),p.second-1));
				}
				if(*((arr+(p.first)*c)+p.second+1)==1){
					q.push(make_pair((p.first),p.second+1));
				}
			}
			else if(p.first==r-1 && p.second==0){
				if(*((arr+(p.first-1)*c)+p.second)==1){
					q.push(make_pair((p.first-1),p.second));
				}
				if(*((arr+(p.first)*c)+p.second+1)==1){
					q.push(make_pair((p.first),p.second+1));
				}
			}
			else if(p.second==0){
				if(*((arr+(p.first-1)*c)+p.second)==1){
					q.push(make_pair((p.first-1),p.second));
				}
				if(*((arr+(p.first+1)*c)+p.second)==1){
					q.push(make_pair((p.first+1),p.second));
				}
				if(*((arr+(p.first)*c)+p.second+1)==1){
					q.push(make_pair((p.first),p.second+1));
				}
			}
			else if(p.first==r-1 && p.second==c-1){
				if(*((arr+(p.first-1)*c)+p.second)==1){
					q.push(make_pair((p.first-1),p.second));
				}
				if(*((arr+(p.first)*c)+p.second-1)==1){
					q.push(make_pair((p.first),p.second-1));
				}
			}
			else if(p.first==r-1){
				if(*((arr+(p.first-1)*c)+p.second)==1){
					q.push(make_pair((p.first-1),p.second));
				}
				if(*((arr+(p.first)*c)+p.second-1)==1){
					q.push(make_pair((p.first),p.second-1));
				}
				if(*((arr+(p.first)*c)+p.second+1)==1){
					q.push(make_pair((p.first),p.second+1));
				}
			}
			else if(p.second==c-1){
				if(*((arr+(p.first-1)*c)+p.second)==1){
					q.push(make_pair((p.first-1),p.second));
				}
				if(*((arr+(p.first+1)*c)+p.second)==1){
					q.push(make_pair((p.first+1),p.second));
				}
				if(*((arr+(p.first)*c)+p.second-1)==1){
					q.push(make_pair((p.first),p.second-1));
				}
			}
			else{
				if(*((arr+(p.first)*c)+p.second-1)==1){
					q.push(make_pair((p.first),p.second-1));
				}
				if(*((arr+(p.first)*c)+p.second+1)==1){
					q.push(make_pair((p.first),p.second+1));
				}
				if(*((arr+(p.first-1)*c)+p.second)==1){
					q.push(make_pair((p.first-1),p.second));
				}
				if(*((arr+(p.first+1)*c)+p.second)==1){
					q.push(make_pair((p.first+1),p.second));
				}
			}
		}
		if(p.first==-1){
			if(!q.empty()){
				q.push(make_pair(-1,-1));
			}
			if(temp==1){
				store++;
				temp=0;
			}
		}
	}
	return store;
}

int main() {
	int num;
	cin>>num;
	
	for(int i=0;i<num;i++){
		int r,c;
		cin>>r>>c;
		int arr[r][c];
		for(int j=0;j<r;j++){
			for(int k=0;k<c;k++){
				cin>>arr[j][k];
			}
		}
		
		int store=rotten(&arr[0][0],r,c);
		if(!zero(&arr[0][0],r,c))
			cout<<"-1"<<endl;
		else
			cout<<store<<endl;
	}
	
	return 0;
}

Output

Number of days are : 2