Table of Contents
Problem Statement
The problem “Minimum time required to rot all oranges” states that you are given a 2D array, every cell has one of the three possible values 0, 1 or 2.
0 means an empty cell.
1 means a fresh orange.
2 means a rotten orange.
If a rotten orange can rot a fresh orange adjacent to it in 1 time unit, find the time taken to rot all the oranges and if it is not possible to rot all the oranges print -1.
Examples
{
{0, 1, 1}
{2, 1, 2}
{1, 0, 1}
}2
{
{0, 1, 0}
{2, 0, 2}
{1, 1, 1}
{1, 1, 1}
}-1
Algorithm to find Minimum time required to rot all oranges
All the rotten oranges are the starting points, they rot the adjacent fresh oranges in 1 unit of time. To find the total time required to rot all the oranges we can do a breadth-first search(BFS) by assuming all the rotten oranges as the starting point of the BFS.
- Create a queue of coordinates, to store the coordinates of required cells, that is, the queue should store the data of the form (row, col). Initialize a variable time as 0.
- Traverse in the given matrix and add the coordinates of all the rotten oranges to the queue.
- While the queue is not empty repeat step 4.
- Initialize a variable size as the size of the queue. Run a loop for i equals 0 to size(not included), and at every iteration pop out an element from the queue. If there is a fresh orange on its adjacent sides(left, right, top and bottom), push the coordinates of that orange to the queue and mark that orange as rotten. If there were some fresh oranges then increment the time by 1 unit.
- Now check if there is some fresh orange still present in the matrix, if yes, all the oranges can not be rotten so return -1, else return time.
Explanation
Consider the example,
{
{0, 1, 1}
{2, 1, 2}
{1, 0, 1}
}
All the oranges are rotten at time = 2.
Code
Java code to find Minimum time required to rot all oranges
import java.util.LinkedList;
import java.util.Queue;
class MinimumTimeRequiredToRotAllOranges {
private static int minTimeToRot(int[][] mat) {
int n = mat.length;
int m = mat[0].length;
// create a queue to store coordinates
Queue<Coordinate> queue = new LinkedList<>();
// initialize a variable time as 0
int time = 0;
// Add all the rotten oranges coordinates to the queue
// these acts as the starting point of the BFS
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 2) {
queue.add(new Coordinate(i, j));
}
}
}
while (!queue.isEmpty()) {
// initialise size as size of queue
int size = queue.size();
// boolean variable representing whether or not an orange
// is rotten in this time unit
boolean isSomeFreshRotten = false;
for (int i = 0; i < size; i++) {
// remove an element from the queue
Coordinate curr = queue.poll();
// generate the coordinates of adjacent cells
// if the generated coordinates are valid and there is a fresh orange
// add the generated coordinates to the queue and mark that orange as rotten
// left adjacent
int leftRow = curr.row - 1;
int leftCol = curr.col;
if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
if (mat[leftRow][leftCol] == 1) {
queue.add(new Coordinate(leftRow, leftCol));
mat[leftRow][leftCol] = 2;
isSomeFreshRotten = true;
}
}
// right adjacent
int rightRow = curr.row + 1;
int rightCol = curr.col;
if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
if (mat[rightRow][rightCol] == 1) {
queue.add(new Coordinate(rightRow, rightCol));
mat[rightRow][rightCol] = 2;
isSomeFreshRotten = true;
}
}
// up adjacent
int upRow = curr.row;
int upCol = curr.col + 1;
if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
if (mat[upRow][upCol] == 1) {
queue.add(new Coordinate(upRow, upCol));
mat[upRow][upCol] = 2;
isSomeFreshRotten = true;
}
}
// down adjacent
int downRow = curr.row;
int downCol = curr.col - 1;
if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
if (mat[downRow][downCol] == 1) {
queue.add(new Coordinate(downRow, downCol));
mat[downRow][downCol] = 2;
isSomeFreshRotten = true;
}
}
}
// if there is some oranges rotten in this time unit,
// increment time else end the BFS here
if (isSomeFreshRotten)
time++;
else
break;
}
// check if there is some fresh oranges in the matrix, if yes return -1
// otherwise return time
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (mat[i][j] == 1)
return -1;
}
}
return time;
}
public static void main(String[] args) {
// Example 1
int mat1[][] = new int[][]{
{0, 1, 1},
{2, 1, 2},
{1, 0, 1}
};
System.out.println(minTimeToRot(mat1));
// Example 2
int mat2[][] = new int[][] {
{0, 1, 0},
{2, 0, 2},
{1, 1, 1},
{1, 1, 1}
};
System.out.println(minTimeToRot(mat2));
}
// class representing a coordinate in the matrix
static class Coordinate {
int row;
int col;
public Coordinate(int row, int col) {
this.row = row;
this.col = col;
}
}
}2 -1
C++ Code to find Minimum time required to rot all oranges
#include<bits/stdc++.h>
using namespace std;
// class representing a coordinate in the matrix
class Coordinate {
public:
int row;
int col;
Coordinate(int r, int c) {
row = r;
col = c;
}
};
int minTimeToRot(vector<vector<int>> &matrix) {
int n = matrix.size();
int m = matrix[0].size();
// create a queue to store coordinates
queue<Coordinate> q;
// initialize a variable time as 0
int time = 0;
// Add all the rotten oranges coordinates to the queue
// these acts as the starting point of the BFS
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 2) {
Coordinate coordinate(i, j);
q.push(coordinate);
}
}
}
while (!q.empty()) {
// initialise size as size of queue
int size = q.size();
bool isSomeFreshRotten = false;
// boolean variable representing whether or not an orange
// is rotten in this time unit
for (int i = 0; i < size; i++) {
// remove an element from the queue
Coordinate curr = q.front();
q.pop();
// generate the coordinates of adjacent cells
// if the generated coordinates are valid and there is a fresh orange
// add the generated coordinates to the queue and mark that orange as rotten
// left adjacent
int leftRow = curr.row - 1;
int leftCol = curr.col;
if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
if (matrix[leftRow][leftCol] == 1) {
Coordinate coordinate(leftRow, leftCol);
q.push(coordinate);
matrix[leftRow][leftCol] = 2;
isSomeFreshRotten = true;
}
}
// right adjacent
int rightRow = curr.row + 1;
int rightCol = curr.col;
if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
if (matrix[rightRow][rightCol] == 1) {
Coordinate coordinate(rightRow, rightCol);
q.push(coordinate);
matrix[rightRow][rightCol] = 2;
isSomeFreshRotten = true;
}
}
// up adjacent
int upRow = curr.row;
int upCol = curr.col + 1;
if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
if (matrix[upRow][upCol] == 1) {
Coordinate coordinate(upRow, upCol);
q.push(coordinate);
matrix[upRow][upCol] = 2;
isSomeFreshRotten = true;
}
}
// down adjacent
int downRow = curr.row;
int downCol = curr.col - 1;
if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
if (matrix[downRow][downCol] == 1) {
Coordinate coordinate(downRow, downCol);
q.push(coordinate);
matrix[downRow][downCol] = 2;
isSomeFreshRotten = true;
}
}
}
// if there is some oranges rotten in this time unit,
// increment time else end the BFS here
if (isSomeFreshRotten) {
time++;
} else {
break;
}
}
// check if there is some fresh oranges in the matrix, if yes return -1
// otherwise return time
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 1)
return -1;
}
}
return time;
}
int main() {
// Example 1
vector<vector<int>> mat1 {
{0, 1, 1},
{2, 1, 2},
{1, 0, 1}
};
cout<<minTimeToRot(mat1)<<endl;
// Example 2
vector<vector<int>> mat2 {
{0, 1, 0},
{2, 0, 2},
{1, 1, 1},
{1, 1, 1}
};
cout<<minTimeToRot(mat2)<<endl;
return 0;
}2 -1
Complexity Analysis
Time Complexity
O(n * m), because we have used breadth First Search which will traverse all the cells in the input matrix. Thus the time complexity is polynomial.
Space Complexity
O(n * m), using BFS takes this space. Because makes use of queue which stores the elements and thus this complexity.
Where n and m are the rows and columns of the given matrix respectively.