Posted on by Kalkicode
Code Probability

# Minimum time required to rot all oranges

The problem of determining the minimum time required to rot all oranges involves finding the shortest time it takes for all the oranges in a given grid to become rotten. In this article, we will provide a step-by-step explanation of the problem and present a Java implementation that solves it efficiently. This solution utilizes a breadth-first search (BFS) algorithm to determine the minimum time required.

## Problem Statement:

Given a grid representing a storage area containing fresh oranges (denoted by 1) and rotten oranges (denoted by 2), the task is to find the minimum time it takes for all the fresh oranges to become rotten. Oranges can rot in four directions: up, down, left, and right. Each minute, all the fresh oranges adjacent to the rotten ones will also become rotten. If it is not possible to rot all the fresh oranges, the algorithm should return -1.

## Approach and Algorithm:

To solve this problem, we can use a BFS-based approach, which explores the grid in a breadth-first manner. The steps of the algorithm are as follows:

1. Create a queue to store the positions of the rotten oranges.
2. Initialize variables for size, time, and temporary row and column values.
3. Iterate through the grid and add the coordinates of the rotten oranges to the queue.
4. Execute a loop until the queue is empty:
• Get the current size of the queue.
• Set a flag variable (result) to false.
• Process each orange in the queue by following these steps:
• Get the position of the current orange from the front of the queue.
• Check the adjacent oranges in all four directions (up, down, left, right).
• If an adjacent orange is fresh (denoted by 1), add it to the queue, change its state to rotten (denoted by 2), and set the result flag to true.
• If the result flag is true, increment the time variable.
5. After the loop ends, check if there are any remaining fresh oranges in the grid. If so, return -1 (indicating that it is not possible to rot all oranges).
6. Otherwise, return the total time taken to rot all oranges.

## Code Solution

``````/*
Java Program for
Minimum time required to rot all oranges
*/

import java.util.Queue;

class Position
{
public int row;
public int col;
public Position(int row, int col)
{
this.row = row;
this.col = col;
}
}
public class Timing
{
public int minTimeToRot(int[][] mat)
{
// Number of row
int n = mat.length;
// Number of columns
int m = mat[0].length;

Queue < Position > queue = new LinkedList <Position> ();

// Define some auxliary variables
int size = 0;
int time = 0;
int tempRow = 0;
int tempCol = 0;
boolean result = true;

// Add cordinate of rot oranges
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mat[i][j] == 2)
{
}
}
}
// Execute this loop unit when queue not empty and result is true
while (!queue.isEmpty() && result == true)
{
// Get the size of queue
size = queue.size();

// Change result
result = false;

// Check of all 4 Direction of rot orange
// Note size is based on queue size
for (int i = 0; i < size; i++)
{
// Get queue element
Position curr = queue.peek();

// Remove queue element
queue.remove();

// Get the position of row and columns
tempRow = curr.row - 1;
tempCol = curr.col;

if ((tempRow >= 0 && tempRow < n) &&
(tempCol >= 0 && tempCol < m) &&
mat[tempRow][tempCol] == 1)
{

// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;

// When change orange
result = true;

}

// Change row
tempRow = curr.row + 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{

// Change right orange
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;

// When change orange
result = true;

}

// Change columns
tempRow = curr.row ;
tempCol = curr.col + 1;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;

}
// Change row
tempRow = curr.row;
// Change columns
tempCol = curr.col - 1;
// Left element
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{

// change orange 1 to 2
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;

}
}

if (result)
{
time++;
}

}

for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mat[i][j] == 1)
{
// In case when orange are not rot
return -1;
}
}
}
return time;
}
public static void main(String[] args)
{
Timing t = new Timing();

int [][]mat1 =
{
{
0 , 1 , 1, 2
},
{
0 , 1 , 0, 0
},
{
0 , 0 , 1, 0
},
{
0 , 1 , 2, 0
}
};
int [][]mat2 =
{
{
1 , 0 , 1, 0
},
{
2 , 0 , 2, 1
},
{
1 , 0 , 0, 0
}
};
int [][]mat3 =
{
{
1 , 0 , 1
},
{
0 , 2 , 0
},
{
1 , 0 , 1
}
};
System.out.println("Result mat1 : "+t.minTimeToRot(mat1));
System.out.println("Result mat2 : "+t.minTimeToRot(mat2));
System.out.println("Result mat3 : "+t.minTimeToRot(mat3));
}
}``````

#### Output

``````Result mat1 : 3
Result mat2 : 1
Result mat3 : -1``````
``````// Include header file
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class Position
{
public: int row;
int col;
Position(int row, int col)
{
this->row = row;
this->col = col;
}
};
class Timing
{
public: int minTimeToRot(vector<vector<int>> &mat)
{
// Number of row
int n = mat.size();
// Number of columns
int m = mat[0].size();
queue < Position *> queue;
// Define some auxliary variables
int size = 0;
int time = 0;
int tempRow = 0;
int tempCol = 0;
bool result = true;
// Add cordinate of rot oranges
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mat[i][j] == 2)
{
queue.push(new Position(i, j));
}
}
}
// Execute this loop unit when queue not empty and result is true
while (!queue.empty() && result == true)
{
// Get the size of queue
size = queue.size();
// Change result
result = false;
// Check of all 4 Direction of rot orange
// Note size is based on queue size
for (int i = 0; i < size; i++)
{
// Get queue element
Position *curr = queue.front();
// Remove queue element
queue.pop();
// Get the position of row and columns
tempRow = curr->row - 1;
tempCol = curr->col;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
queue.push(new Position(tempRow, tempCol));
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr->row + 1;
tempCol = curr->col;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
// Change right orange
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
queue.push(new Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr->row;
tempCol = curr->col + 1;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
queue.push(new Position(tempRow, tempCol));
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr->row;
// Change columns
tempCol = curr->col - 1;
// Left element
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
queue.push(new Position(tempRow, tempCol));
// change orange 1 to 2
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
}
if (result)
{
time++;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mat[i][j] == 1)
{
// In case when orange are not rot
return -1;
}
}
}
return time;
}
};
int main()
{
Timing *t = new Timing();
vector<vector<int>> mat1{
{
0 , 1 , 1 , 2
} , {
0 , 1 , 0 , 0
} , {
0 , 0 , 1 , 0
} , {
0 , 1 , 2 , 0
}
};
vector<vector<int>> mat2{
{
1 , 0 , 1 , 0
} , {
2 , 0 , 2 , 1
} , {
1 , 0 , 0 , 0
}
};
vector<vector<int>> mat3{
{
1 , 0 , 1
} , {
0 , 2 , 0
} , {
1 , 0 , 1
}
};
cout << "Result mat1 : " << t->minTimeToRot(mat1) << endl;
cout << "Result mat2 : " << t->minTimeToRot(mat2) << endl;
cout << "Result mat3 : " << t->minTimeToRot(mat3) << endl;
return 0;
}``````

#### Output

``````Result mat1 : 3
Result mat2 : 1
Result mat3 : -1``````
``````// Include namespace system
using System;
using System.Collections.Generic;
public class Position
{
public int row;
public int col;
public Position(int row, int col)
{
this.row = row;
this.col = col;
}
}
public class Timing
{
public int minTimeToRot(int[,] mat)
{
// Number of row
int n = mat.GetLength(0);
// Number of columns
int m = mat.GetLength(1);
Queue < Position > queue = new Queue < Position > ();
// Define some auxliary variables
int size = 0;
int time = 0;
int tempRow = 0;
int tempCol = 0;
Boolean result = true;
// Add cordinate of rot oranges
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mat[i,j] == 2)
{
queue.Enqueue(new Position(i, j));
}
}
}
// Execute this loop unit when queue not empty and result is true
while ((queue.Count != 0) && result == true)
{
// Get the size of queue
size = queue.Count;
// Change result
result = false;
// Check of all 4 Direction of rot orange
// Note size is based on queue size
for (int i = 0; i < size; i++)
{
// Get queue element
Position curr = queue.Peek();
// Remove queue element
queue.Dequeue();
// Get the position of row and columns
tempRow = curr.row - 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow,tempCol] == 1)
{
queue.Enqueue(new Position(tempRow, tempCol));
// Fresh orange to rot orange
mat[tempRow,tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row + 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow,tempCol] == 1)
{
// Change right orange
// Fresh orange to rot orange
mat[tempRow,tempCol] = 2;
queue.Enqueue(new Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow,tempCol] == 1)
{
queue.Enqueue(new Position(tempRow, tempCol));
// Fresh orange to rot orange
mat[tempRow,tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row;
// Change columns
tempCol = curr.col - 1;
// Left element
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow,tempCol] == 1)
{
queue.Enqueue(new Position(tempRow, tempCol));
// change orange 1 to 2
// Fresh orange to rot orange
mat[tempRow,tempCol] = 2;
// When change orange
result = true;
}
}
if (result)
{
time++;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (mat[i,j] == 1)
{
// In case when orange are not rot
return -1;
}
}
}
return time;
}
public static void Main(String[] args)
{
Timing t = new Timing();
int[,] mat1 = {
{
0 , 1 , 1 , 2
},
{
0 , 1 , 0 , 0
},
{
0 , 0 , 1 , 0
},
{
0 , 1 , 2 , 0
}
};
int[,] mat2 = {
{
1 , 0 , 1 , 0
},
{
2 , 0 , 2 , 1
},
{
1 , 0 , 0 , 0
}
};
int[,] mat3 = {
{
1 , 0 , 1
},
{
0 , 2 , 0
},
{
1 , 0 , 1
}
};
Console.WriteLine("Result mat1 : " + t.minTimeToRot(mat1));
Console.WriteLine("Result mat2 : " + t.minTimeToRot(mat2));
Console.WriteLine("Result mat3 : " + t.minTimeToRot(mat3));
}
}``````

#### Output

``````Result mat1 : 3
Result mat2 : 1
Result mat3 : -1``````
``````<?php
/*
Php Program for
Minimum time required to rot all oranges
*/
class Position
{
public \$row;
public \$col;
public	function __construct(\$row, \$col)
{
\$this->row = \$row;
\$this->col = \$col;
}
}
class Timing
{
public	function minTimeToRot(\$mat)
{
// Number of row
\$n = count(\$mat);
// Number of columns
\$m = count(\$mat[0]);
\$queue = array();
// Define some auxliary variables
\$size = 0;
\$time = 0;
\$tempRow = 0;
\$tempCol = 0;
\$result = true;
// Add cordinate of rot oranges
for (\$i = 0; \$i < \$n; \$i++)
{
for (\$j = 0; \$j < \$m; \$j++)
{
if (\$mat[\$i][\$j] == 2)
{
array_unshift(\$queue, new Position(\$i, \$j));
}
}
}
// Execute this loop unit when queue not empty and result is true
while ((count(\$queue) > 0) && \$result == true)
{
// Get the size of queue
\$size = count(\$queue);
// Change result
\$result = false;
// Check of all 4 Direction of rot orange
// Note size is based on queue size
for (\$i = 0; \$i < \$size; \$i++)
{
// Get queue element
\$curr = end(\$queue);
// Remove queue element
array_pop(\$queue);
// Get the position of row and columns
\$tempRow = \$curr->row - 1;
\$tempCol = \$curr->col;
if ((\$tempRow >= 0 && \$tempRow < \$n)
&& (\$tempCol >= 0 && \$tempCol < \$m)
&& \$mat[\$tempRow][\$tempCol] == 1)
{
array_unshift(\$queue, new Position(\$tempRow, \$tempCol));
// Fresh orange to rot orange
\$mat[\$tempRow][\$tempCol] = 2;
// When change orange
\$result = true;
}
// Change row
\$tempRow = \$curr->row + 1;
\$tempCol = \$curr->col;
if ((\$tempRow >= 0 && \$tempRow < \$n)
&& (\$tempCol >= 0 && \$tempCol < \$m)
&& \$mat[\$tempRow][\$tempCol] == 1)
{
// Change right orange
// Fresh orange to rot orange
\$mat[\$tempRow][\$tempCol] = 2;
array_unshift(\$queue, new Position(\$tempRow, \$tempCol));
// When change orange
\$result = true;
}
// Change columns
\$tempRow = \$curr->row;
\$tempCol = \$curr->col + 1;
if ((\$tempRow >= 0 && \$tempRow < \$n)
&& (\$tempCol >= 0 && \$tempCol < \$m)
&& \$mat[\$tempRow][\$tempCol] == 1)
{
array_unshift(\$queue, new Position(\$tempRow, \$tempCol));
// Fresh orange to rot orange
\$mat[\$tempRow][\$tempCol] = 2;
// When change orange
\$result = true;
}
// Change row
\$tempRow = \$curr->row;
// Change columns
\$tempCol = \$curr->col - 1;
// Left element
if ((\$tempRow >= 0 && \$tempRow < \$n)
&& (\$tempCol >= 0 && \$tempCol < \$m)
&& \$mat[\$tempRow][\$tempCol] == 1)
{
array_unshift(\$queue, new Position(\$tempRow, \$tempCol));
// change orange 1 to 2
// Fresh orange to rot orange
\$mat[\$tempRow][\$tempCol] = 2;
// When change orange
\$result = true;
}
}
if (\$result)
{
\$time++;
}
}
for (\$i = 0; \$i < \$n; \$i++)
{
for (\$j = 0; \$j < \$m; \$j++)
{
if (\$mat[\$i][\$j] == 1)
{
// In case when orange are not rot
return -1;
}
}
}
return \$time;
}
}

function main()
{
\$t = new Timing();
\$mat1 = array(
array(0, 1, 1, 2),
array(0, 1, 0, 0),
array(0, 0, 1, 0),
array(0, 1, 2, 0)
);
\$mat2 = array(
array(1, 0, 1, 0),
array(2, 0, 2, 1),
array(1, 0, 0, 0)
);
\$mat3 = array(
array(1, 0, 1),
array(0, 2, 0),
array(1, 0, 1)
);
echo("Result mat1 : ".\$t->minTimeToRot(\$mat1).
"\n");
echo("Result mat2 : ".\$t->minTimeToRot(\$mat2).
"\n");
echo("Result mat3 : ".\$t->minTimeToRot(\$mat3).
"\n");
}
main();``````

#### Output

``````Result mat1 : 3
Result mat2 : 1
Result mat3 : -1``````
``````class Position
{
constructor(row, col)
{
this.row = row;
this.col = col;
}
}
class Timing
{
minTimeToRot(mat)
{
// Number of row
var n = mat.length;
// Number of columns
var m = mat[0].length;
var queue = [];
// Define some auxliary variables
var size = 0;
var time = 0;
var tempRow = 0;
var tempCol = 0;
var result = true;
// Add cordinate of rot oranges
for (var i = 0; i < n; i++)
{
for (var j = 0; j < m; j++)
{
if (mat[i][j] == 2)
{
queue.push(new Position(i, j));
}
}
}
// Execute this loop unit when queue not empty and result is true
while ((queue.length > 0) && result == true)
{
// Get the size of queue
size = queue.length;
// Change result
result = false;
// Check of all 4 Direction of rot orange
// Note size is based on queue size
for (var i = 0; i < size; i++)
{
// Get queue element
var curr = queue[0];
// Remove queue element
queue.shift();
// Get the position of row and columns
tempRow = curr.row - 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
queue.push(new Position(tempRow, tempCol));
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row + 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
// Change right orange
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
queue.push(new Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
queue.push(new Position(tempRow, tempCol));
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row;
// Change columns
tempCol = curr.col - 1;
// Left element
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
queue.push(new Position(tempRow, tempCol));
// change orange 1 to 2
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
}
if (result)
{
time++;
}
}
for (var i = 0; i < n; i++)
{
for (var j = 0; j < m; j++)
{
if (mat[i][j] == 1)
{
// In case when orange are not rot
return -1;
}
}
}
return time;
}
}

function main()
{
var t = new Timing();
var mat1 = [
[0, 1, 1, 2],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 1, 2, 0]
];
var mat2 = [
[1, 0, 1, 0],
[2, 0, 2, 1],
[1, 0, 0, 0]
];
var mat3 = [
[1, 0, 1],
[0, 2, 0],
[1, 0, 1]
];
console.log("Result mat1 : " + t.minTimeToRot(mat1));
console.log("Result mat2 : " + t.minTimeToRot(mat2));
console.log("Result mat3 : " + t.minTimeToRot(mat3));
}
main();``````

#### Output

``````Result mat1 : 3
Result mat2 : 1
Result mat3 : -1``````
``````#    Python 3 Program for
#    Minimum time required to rot all oranges
class Position :
def __init__(self, row, col) :
self.row = row
self.col = col

class Timing :
def minTimeToRot(self, mat) :
#  Number of row
n = len(mat)
#  Number of columns
m = len(mat[0])
queue = []
#  Define some auxliary variables
size = 0
time = 0
tempRow = 0
tempCol = 0
result = True
i = 0
#  Add cordinate of rot oranges
while (i < n) :
j = 0
while (j < m) :
if (mat[i][j] == 2) :
queue.append(Position(i, j))

j += 1

i += 1

#  Execute this loop unit when queue not empty and result is true
while ((len(queue) > 0) and result == True) :
#  Get the size of queue
size = len(queue)
#  Change result
result = False
i = 0
#  Check of all 4 Direction of rot orange
#  Note size is based on queue size
while (i < size and len(queue) > 0) :
#  Get queue element
curr = queue[0]
#  Remove queue element
queue.pop(0)
#  Get the position of row and columns
tempRow = curr.row - 1
tempCol = curr.col
if ((tempRow >= 0 and tempRow < n) and
(tempCol >= 0 and tempCol < m) and
mat[tempRow][tempCol] == 1) :
queue.append(Position(tempRow, tempCol))
#  Fresh orange to rot orange
mat[tempRow][tempCol] = 2
#  When change orange
result = True

#  Change row
tempRow = curr.row + 1
tempCol = curr.col
if ((tempRow >= 0 and tempRow < n) and
(tempCol >= 0 and tempCol < m) and
mat[tempRow][tempCol] == 1) :
#  Change right orange
#  Fresh orange to rot orange
mat[tempRow][tempCol] = 2
queue.append(Position(tempRow, tempCol))
#  When change orange
result = True

#  Change columns
tempRow = curr.row
tempCol = curr.col + 1
if ((tempRow >= 0 and tempRow < n) and
(tempCol >= 0 and tempCol < m) and
mat[tempRow][tempCol] == 1) :
queue.append(Position(tempRow, tempCol))
#  Fresh orange to rot orange
mat[tempRow][tempCol] = 2
#  When change orange
result = True

#  Change row
tempRow = curr.row
#  Change columns
tempCol = curr.col - 1
#  Left element
if ((tempRow >= 0 and tempRow < n) and
(tempCol >= 0 and tempCol < m) and
mat[tempRow][tempCol] == 1) :
queue.append(Position(tempRow, tempCol))
#  change orange 1 to 2
#  Fresh orange to rot orange
mat[tempRow][tempCol] = 2
#  When change orange
result = True

i += 1

if (result) :
time += 1

i = 0
while (i < n) :
j = 0
while (j < m) :
if (mat[i][j] == 1) :
#  In case when orange are not rot
return -1

j += 1

i += 1

return time

def main() :
t = Timing()
mat1 = [
[0, 1, 1, 2],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 1, 2, 0]
]
mat2 = [
[1, 0, 1, 0],
[2, 0, 2, 1],
[1, 0, 0, 0]
]
mat3 = [
[1, 0, 1],
[0, 2, 0],
[1, 0, 1]
]
print("Result mat1 : ", t.minTimeToRot(mat1))
print("Result mat2 : ", t.minTimeToRot(mat2))
print("Result mat3 : ", t.minTimeToRot(mat3))

if __name__ == "__main__": main()``````

#### Output

``````Result mat1 :  3
Result mat2 :  1
Result mat3 :  -1``````
``````#    Ruby Program for
#    Minimum time required to rot all oranges
class Position
# Define the accessor and reader of class Position
attr_accessor :row, :col
def initialize(row, col)
self.row = row
self.col = col
end
end

class Timing
def minTimeToRot(mat)
#  Number of row
n = mat.length
#  Number of columns
m = mat[0].length

record = []
#  Define some auxliary variables
size = 0
times = 0
tempRow = 0
tempCol = 0
result = true
i = 0
#  Add cordinate of rot oranges
while (i < n)
j = 0
while (j < m)
if (mat[i][j] == 2)
record.push(Position.new(i, j))
end

j += 1
end

i += 1
end

#  Execute this loop unit when record not empty and result is true
while ((record.length > 0) && result == true)
#  Get the size of record
size = record.length

#  Change result
result = false
i = 0
#  Check of all 4 Direction of rot orange
#  Note size is based on record size
while (i < size && record.length > 0)
#  Get record element
curr = record.first()
x = curr.row
y = curr.col
#  Remove record element
record = record.drop(1)
#  Get the position of row and columns
tempRow = x - 1
tempCol = y
if ((tempRow >= 0 && tempRow < n)  &&
(tempCol >= 0 && tempCol < m) &&
(mat[tempRow][tempCol] == 1))
record.push(Position.new(tempRow, tempCol))
#  Fresh orange to rot orange
mat[tempRow][tempCol] = 2
#  When change orange
result = true
end

#  Change row
tempRow = x + 1
tempCol = y
if ((tempRow >= 0 && tempRow < n) &&
(tempCol >= 0 && tempCol < m) &&
(mat[tempRow][tempCol] == 1) )
#  Change right orange
#  Fresh orange to rot orange
mat[tempRow][tempCol] = 2
record.push(Position.new(tempRow, tempCol))
#  When change orange
result = true
end

#  Change columns
tempRow = x
tempCol = y + 1
if ((tempRow >= 0 && tempRow < n) &&
(tempCol >= 0 && tempCol < m) &&
(mat[tempRow][tempCol] == 1) )
record.push(Position.new(tempRow, tempCol))
#  Fresh orange to rot orange
mat[tempRow][tempCol] = 2
#  When change orange
result = true
end

#  Change row
tempRow = x
#  Change columns
tempCol = y - 1
#  Left element
if ((tempRow >= 0 && tempRow < n) &&
(mat[tempRow][tempCol] == 1) &&
(tempCol >= 0 && tempCol < m) )
record.push(Position.new(tempRow, tempCol))
#  change orange 1 to 2
#  Fresh orange to rot orange
mat[tempRow][tempCol] = 2
#  When change orange
result = true
end

i += 1
end

if (result)
times = times + 1
end

end

i = 0
while (i < n)
j = 0
while (j < m)
if (mat[i][j] == 1)
#  In case when orange are not rot
return -1
end

j += 1
end

i += 1
end

return times
end

end

def main()
t = Timing.new()
mat1 = [
[0, 1, 1, 2],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 1, 2, 0]
]
mat2 = [
[1, 0, 1, 0],
[2, 0, 2, 1],
[1, 0, 0, 0]
]
mat3 = [
[1, 0, 1],
[0, 2, 0],
[1, 0, 1]
]
print("Result mat1 : ", t.minTimeToRot(mat1), "\n")
print("Result mat2 : ", t.minTimeToRot(mat2), "\n")
print("Result mat3 : ", t.minTimeToRot(mat3), "\n")
end

main()``````

#### Output

``````Result mat1 : 3
Result mat2 : 1
Result mat3 : -1
``````
``````import scala.collection.mutable._;
/*
Scala Program for
Minimum time required to rot all oranges
*/
class Position(var row: Int,
var col: Int)
{

}
class Timing()
{
def minTimeToRot(mat: Array[Array[Int]]): Int = {
// Number of row
var n: Int = mat.length;
// Number of columns
var m: Int = mat(0).length;
var queue: Queue[Position] = new Queue[Position]();
// Define some auxliary variables
var size: Int = 0;
var time: Int = 0;
var tempRow: Int = 0;
var tempCol: Int = 0;
var result: Boolean = true;
var i: Int = 0;
// Add cordinate of rot oranges
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (mat(i)(j) == 2)
{
queue.enqueue(new Position(i, j));
}
j += 1;
}
i += 1;
}
// Execute this loop unit when queue not empty and result is true
while (!queue.isEmpty && result == true)
{
// Get the size of queue
size = queue.size;
// Change result
result = false;
i = 0;
// Check of all 4 Direction of rot orange
// Note size is based on queue size
while (i < size)
{
// Get queue element
var curr: Position = queue.front;
// Remove queue element
queue.dequeue;
// Get the position of row and columns
tempRow = curr.row - 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
{
queue.enqueue(new Position(tempRow, tempCol));
// Fresh orange to rot orange
mat(tempRow)(tempCol) = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row + 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
{
// Change right orange
// Fresh orange to rot orange
mat(tempRow)(tempCol) = 2;
queue.enqueue(new Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
{
queue.enqueue(new Position(tempRow, tempCol));
// Fresh orange to rot orange
mat(tempRow)(tempCol) = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row;
// Change columns
tempCol = curr.col - 1;
// Left element
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
{
queue.enqueue(new Position(tempRow, tempCol));
// change orange 1 to 2
// Fresh orange to rot orange
mat(tempRow)(tempCol) = 2;
// When change orange
result = true;
}
i += 1;
}
if (result)
{
time += 1;
}
}
i = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (mat(i)(j) == 1)
{
// In case when orange are not rot
return -1;
}
j += 1;
}
i += 1;
}
return time;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var t: Timing = new Timing();
var mat1: Array[Array[Int]] = Array(
Array(0, 1, 1, 2),
Array(0, 1, 0, 0),
Array(0, 0, 1, 0),
Array(0, 1, 2, 0)
);
var mat2: Array[Array[Int]] = Array(
Array(1, 0, 1, 0),
Array(2, 0, 2, 1),
Array(1, 0, 0, 0)
);
var mat3: Array[Array[Int]] = Array(
Array(1, 0, 1),
Array(0, 2, 0),
Array(1, 0, 1)
);
println("Result mat1 : " + t.minTimeToRot(mat1));
println("Result mat2 : " + t.minTimeToRot(mat2));
println("Result mat3 : " + t.minTimeToRot(mat3));
}
}``````

#### Output

``````Result mat1 : 3
Result mat2 : 1
Result mat3 : -1``````
``````import Foundation;
/*
Swift 4 Program for
Minimum time required to rot all oranges
*/
class Position
{
var row: Int;
var col: Int;
init(_ row: Int, _ col: Int)
{
self.row = row;
self.col = col;
}
}
class Timing
{
func minTimeToRot(_ mat: inout[[Int]]) -> Int
{
// Number of row
let n: Int = mat.count;
// Number of columns
let m: Int = mat[0].count;
var queue = [Position]();
// Define some auxliary variables
var size: Int = 0;
var time: Int = 0;
var tempRow: Int = 0;
var tempCol: Int = 0;
var result: Bool = true;
var i: Int = 0;
// Add cordinate of rot oranges
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (mat[i][j] == 2)
{
queue.append(Position(i, j));
}
j += 1;
}
i += 1;
}
// Execute this loop unit when queue not empty and result is true
while ((queue.count > 0) && result == true)
{
// Get the size of queue
size = queue.count;
// Change result
result = false;
i  = 0;
// Check of all 4 Direction of rot orange
// Note size is based on queue size
while (i < size)
{
// Get queue element
let curr: Position = queue[0];
// Remove queue element
queue.removeFirst();
// Get the position of row and columns
tempRow = curr.row - 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
queue.append(Position(tempRow, tempCol));
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row + 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
// Change right orange
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
queue.append(Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
queue.append(Position(tempRow, tempCol));
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row;
// Change columns
tempCol = curr.col - 1;
// Left element
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
queue.append(Position(tempRow, tempCol));
// change orange 1 to 2
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
i += 1;
}
if (result)
{
time += 1;
}
}
i = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (mat[i][j] == 1)
{
// In case when orange are not rot
return -1;
}
j += 1;
}
i += 1;
}
return time;
}
}
func main()
{
let t: Timing = Timing();
var mat1: [
[Int]
] = [
[0, 1, 1, 2],
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 1, 2, 0]
];
var mat2: [
[Int]
] = [
[1, 0, 1, 0],
[2, 0, 2, 1],
[1, 0, 0, 0]
];
var mat3: [
[Int]
] = [
[1, 0, 1],
[0, 2, 0],
[1, 0, 1]
];
print("Result mat1 : ", t.minTimeToRot(&mat1));
print("Result mat2 : ", t.minTimeToRot(&mat2));
print("Result mat3 : ", t.minTimeToRot(&mat3));
}
main();``````

#### Output

``````Result mat1 :  3
Result mat2 :  1
Result mat3 :  -1``````
``````/*
Kotlin Program for
Minimum time required to rot all oranges
*/
import java.util.Queue
class Position
{
var row: Int;
var col: Int;
constructor(row: Int, col: Int)
{
this.row = row;
this.col = col;
}
}
class Timing
{
fun minTimeToRot(mat: Array < Array < Int >> ): Int
{
// Number of row
val n: Int = mat.count();
// Number of columns
val m: Int = mat[0].count();
var queue: Queue < Position > = LinkedList < Position > ();
// Define some auxliary variables
var size: Int ;
var time: Int = 0;
var tempRow: Int;
var tempCol: Int ;
var result: Boolean = true;
var i: Int = 0;
// Add cordinate of rot oranges
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (mat[i][j] == 2)
{
}
j += 1;
}
i += 1;
}
// Execute this loop unit when queue not empty and result is true
while (!queue.isEmpty() && result == true)
{
// Get the size of queue
size = queue.size;
// Change result
result = false;
i = 0;
// Check of all 4 Direction of rot orange
// Note size is based on queue size
while (i < size)
{
// Get queue element
val curr: Position = queue.peek();
// Remove queue element
queue.remove();
// Get the position of row and columns
tempRow = curr.row - 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
{
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row + 1;
tempCol = curr.col;
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
{
// Change right orange
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
{
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
// Change row
tempRow = curr.row;
// Change columns
tempCol = curr.col - 1;
// Left element
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
{
// change orange 1 to 2
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2;
// When change orange
result = true;
}
i += 1;
}
if (result)
{
time += 1;
}
}
i = 0;
while (i < n)
{
var j: Int = 0;
while (j < m)
{
if (mat[i][j] == 1)
{
// In case when orange are not rot
return -1;
}
j += 1;
}
i += 1;
}
return time;
}
}
fun main(args: Array < String > ): Unit
{
val t: Timing = Timing();
val mat1: Array < Array < Int >> = arrayOf(arrayOf(0, 1, 1, 2), arrayOf(0, 1, 0, 0), arrayOf(0, 0, 1, 0), arrayOf(0, 1, 2, 0));
val mat2: Array < Array < Int >> = arrayOf(arrayOf(1, 0, 1, 0), arrayOf(2, 0, 2, 1), arrayOf(1, 0, 0, 0));
val mat3: Array < Array < Int >> = arrayOf(arrayOf(1, 0, 1), arrayOf(0, 2, 0), arrayOf(1, 0, 1));
println("Result mat1 : " + t.minTimeToRot(mat1));
println("Result mat2 : " + t.minTimeToRot(mat2));
println("Result mat3 : " + t.minTimeToRot(mat3));
}``````

#### Output

``````Result mat1 : 3
Result mat2 : 1
Result mat3 : -1``````
``````package main
import "fmt"
/*
Go Program for
Minimum time required to rot all oranges
*/
type Position struct {
row int
col int
}
func getPosition(row int, col int) * Position {
var me * Position = & Position {}
me.row = row
me.col = col
return me
}
type Timing struct {}
func getTiming() * Timing {
var me * Timing = & Timing {}
return me
}
func(this Timing) minTimeToRot(mat[][] int) int {
// Number of row
var n int = len(mat)
// Number of columns
var m int = len(mat[0])
var queue[] * Position
// Define some auxliary variables
var size int = 0
var time int = 0
var tempRow int = 0
var tempCol int = 0
var result bool = true
// Add cordinate of rot oranges
for i:= 0; i < n; i++{
for j:= 0;j < m;j++{
if mat[i][j] == 2 {
queue = append(queue, getPosition(i, j))
}
}
}
// Execute this loop unit when queue not empty and result is true
for ((len(queue) > 0) && result == true) {
// Get the size of queue
size = len(queue)
// Change result
result = false
// Check of all 4 Direction of rot orange
// Note size is based on queue size
for i:= 0 ; i < size; i++{
// Get queue element
var curr * Position = queue[0]
// Remove queue element
queue = queue[1: ]
// Get the position of row and columns
tempRow = curr.row - 1
tempCol = curr.col
if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
queue = append(queue, getPosition(tempRow, tempCol))
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2
// When change orange
result = true
}
// Change row
tempRow = curr.row + 1
tempCol = curr.col
if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
// Change right orange
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2
queue = append(queue, getPosition(tempRow, tempCol))
// When change orange
result = true
}
// Change columns
tempRow = curr.row
tempCol = curr.col + 1
if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
queue = append(queue, getPosition(tempRow, tempCol))
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2
// When change orange
result = true
}
// Change row
tempRow = curr.row
// Change columns
tempCol = curr.col - 1
// Left element
if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
queue = append(queue, getPosition(tempRow, tempCol))
// change orange 1 to 2
// Fresh orange to rot orange
mat[tempRow][tempCol] = 2
// When change orange
result = true
}
}
if result {
time++
}
}
for i:= 0; i < n; i++{
for j:= 0; j < m; j++{
if mat[i][j] == 1 {
// In case when orange are not rot
return -1
}
}
}
return time
}
func main() {
var t * Timing = getTiming()
var mat1 = [][] int {
{
0,
1,
1,
2,
}, {
0,
1,
0,
0,
}, {
0,
0,
1,
0,
}, {
0,
1,
2,
0,
},
}
var mat2 = [][] int {
{
1,
0,
1,
0,
}, {
2,
0,
2,
1,
}, {
1,
0,
0,
0,
},
}
var mat3 = [][] int {
{
1,
0,
1,
}, {
0,
2,
0,
}, {
1,
0,
1,
},
}
fmt.Println("Result mat1 : ", t.minTimeToRot(mat1))
fmt.Println("Result mat2 : ", t.minTimeToRot(mat2))
fmt.Println("Result mat3 : ", t.minTimeToRot(mat3))
}``````

#### Output

``````Result mat1 : 3
Result mat2 : 1
Result mat3 : -1``````

The time complexity of the above code is O(N * M), where N is the number of rows in the grid and M is the number of columns.

Explanation:

1. Adding Rotten Oranges to the Queue:

• In the worst case, all elements in the grid can be rotten oranges, resulting in a total of N * M elements being added to the queue.
• This process has a time complexity of O(N * M).
2. Performing BFS:

• The while loop executes as long as the queue is not empty.
• In each iteration, we process the oranges in the queue, which is determined by the size of the queue at the beginning of the iteration.
• The maximum number of elements that can be present in the queue is N * M (all the oranges in the grid).
• Thus, the while loop can execute a maximum of N * M times in the worst case.
• Inside the loop, we perform constant time operations (adding coordinates to the queue, changing orange states, updating flags).
• Therefore, the time complexity of the while loop is O(N * M).
3. Checking Remaining Fresh Oranges:

• After the BFS loop, we iterate through the entire grid once to check if there are any remaining fresh oranges.
• This iteration has a time complexity of O(N * M) since we need to check each element in the grid.

Overall, the time complexity of the code is dominated by the BFS loop, resulting in a total time complexity of O(N * M).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post