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:
- Create a queue to store the positions of the rotten oranges.
- Initialize variables for size, time, and temporary row and column values.
- Iterate through the grid and add the coordinates of the rotten oranges to the queue.
- 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.
- 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).
- 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.LinkedList;
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)
{
queue.add(new Position(i, j));
}
}
}
// 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();
// Up element adjustment
// 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)
{
// Add change coordinate
queue.add(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;
// Down element adjustment
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;
// Add change cordinate
queue.add(new Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row ;
tempCol = curr.col + 1;
// Right element adjustment
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
// Add change coordinate
queue.add(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)
{
// Add change coordinate
queue.add(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
}
};
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();
// Up element adjustment
// 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)
{
// Add change coordinate
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;
// Down element adjustment
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;
// Add change cordinate
queue.push(new Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr->row;
tempCol = curr->col + 1;
// Right element adjustment
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
// Add change coordinate
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)
{
// Add change coordinate
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();
// Up element adjustment
// 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)
{
// Add change coordinate
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;
// Down element adjustment
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;
// Add change cordinate
queue.Enqueue(new Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
// Right element adjustment
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow,tempCol] == 1)
{
// Add change coordinate
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)
{
// Add change coordinate
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);
// Up element adjustment
// 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)
{
// Add change coordinate
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;
// Down element adjustment
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;
// Add change cordinate
array_unshift($queue, new Position($tempRow, $tempCol));
// When change orange
$result = true;
}
// Change columns
$tempRow = $curr->row;
$tempCol = $curr->col + 1;
// Right element adjustment
if (($tempRow >= 0 && $tempRow < $n)
&& ($tempCol >= 0 && $tempCol < $m)
&& $mat[$tempRow][$tempCol] == 1)
{
// Add change coordinate
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)
{
// Add change coordinate
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 : -1class 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();
// Up element adjustment
// 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)
{
// Add change coordinate
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;
// Down element adjustment
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;
// Add change cordinate
queue.push(new Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
// Right element adjustment
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
// Add change coordinate
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)
{
// Add change coordinate
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)
# Up element adjustment
# 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) :
# Add change coordinate
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
# Down element adjustment
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
# Add change cordinate
queue.append(Position(tempRow, tempCol))
# When change orange
result = True
# Change columns
tempRow = curr.row
tempCol = curr.col + 1
# Right element adjustment
if ((tempRow >= 0 and tempRow < n) and
(tempCol >= 0 and tempCol < m) and
mat[tempRow][tempCol] == 1) :
# Add change coordinate
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) :
# Add change coordinate
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_reader :row, :col
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)
# Up element adjustment
# 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))
# Add change coordinate
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
# Down element adjustment
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
# Add change cordinate
record.push(Position.new(tempRow, tempCol))
# When change orange
result = true
end
# Change columns
tempRow = x
tempCol = y + 1
# Right element adjustment
if ((tempRow >= 0 && tempRow < n) &&
(tempCol >= 0 && tempCol < m) &&
(mat[tempRow][tempCol] == 1) )
# Add change coordinate
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) )
# Add change coordinate
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;
// Up element adjustment
// 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)
{
// Add change coordinate
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;
// Down element adjustment
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;
// Add change cordinate
queue.enqueue(new Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
// Right element adjustment
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat(tempRow)(tempCol) == 1)
{
// Add change coordinate
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)
{
// Add change coordinate
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 : -1import 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();
// Up element adjustment
// 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)
{
// Add change coordinate
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;
// Down element adjustment
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;
// Add change cordinate
queue.append(Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
// Right element adjustment
if ((tempRow >= 0 && tempRow < n)
&& (tempCol >= 0 && tempCol < m)
&& mat[tempRow][tempCol] == 1)
{
// Add change coordinate
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)
{
// Add change coordinate
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
import java.util.LinkedList
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)
{
queue.add(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
val curr: Position = queue.peek();
// Remove queue element
queue.remove();
// Up element adjustment
// 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)
{
// Add change coordinate
queue.add(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;
// Down element adjustment
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;
// Add change cordinate
queue.add(Position(tempRow, tempCol));
// When change orange
result = true;
}
// Change columns
tempRow = curr.row;
tempCol = curr.col + 1;
// Right element adjustment
if ((tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1)
{
// Add change coordinate
queue.add(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)
{
// Add change coordinate
queue.add(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;
}
}
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 : -1package 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: ]
// Up element adjustment
// 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 {
// Add change coordinate
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
// Down element adjustment
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
// Add change cordinate
queue = append(queue, getPosition(tempRow, tempCol))
// When change orange
result = true
}
// Change columns
tempRow = curr.row
tempCol = curr.col + 1
// Right element adjustment
if (tempRow >= 0 && tempRow < n) && (tempCol >= 0 && tempCol < m) && mat[tempRow][tempCol] == 1 {
// Add change coordinate
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 {
// Add change coordinate
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 : -1The 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:
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).
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).
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).
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.
New Comment