# Maximum time to rot all oranges

• You are given a matrix of dimensions m*n 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 so that all the oranges will be rotten,assuming it takes one second to rot the immediate neighbours. A rotten orange at index `[i,j]` can rot other fresh orange at indexes `[i+1,j] ,[i,j+1] ,[i-1,j] ,[i,j-1]`. If it is impossible to rot every orange then simply return `-1`

• what is the initial arrangement of 0,1,2s in the matrix?

• The arrangement is not pre-defined. The solution should find out the time for any arrangement of 0,1,2s.

• A brute force solution is here. The time complexity is O(n^2m^2) which is really bad and I think it can be improved.
Basically the idea is to keep on rotting the neighbors of a cell containing 2, one by one and counting the iterations. After reaching the maximum iterations of n
m, if we still have oranges that aren't rot it means that there is no solution so return -1.`enter code here`

{
/**

• You are given a matrix of dimensions m*n 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 so that all the oranges will be rotten,assuming

• it takes one second to rot the immediate neighbors. A rotten orange at index

• [i,j] can rot other fresh orange at indexes [i+1,j] ,[i,j+1] ,[i-1,j]

• ,[i,j-1]. If it is impossible to rot every orange then simply return -1

• @author shivam.maharshi
*/
public class MaxTimeToRotAllOranges {

private static int[] xa = new int[] { 0, 0, -1, 1 };
private static int[] ya = new int[] { -1, 1, 0, 0 };

/*

• Time Complexity: O(n^2*m^2). Which is really bad and can be improved.
/
public static int getTime(int[][] a) {
int count = 0;
// Scope of improving time complexity here from O(n
m).
while (count < a.length * a[0].length) {
if (allRotten(a))
return count;
count++;
Set<Cell> s = rotNeighbors(a);
for (Cell c : s) {
a[c.x][c.y] = 2;
}
}
return -1;
}

// Time Complexity: O(n*m)
private static Set<Cell> rotNeighbors(int[][] a) {
Set<Cell> list = new HashSet<>();
for (int x = 0; x < a.length; x++) {
for (int y = 0; y < a[0].length; y++) {
if (a[x][y] == 2) {
for (int k = 0; k < 4; k++) {
int nextX = x + xa[k];
int nextY = y + ya[k];
if (isValid(a, nextX, nextY) && a[nextX][nextY] == 1) {
}
}
}
}
}
return list;
}

private static boolean isValid(int[][] a, int x, int y) {
return (x >= 0 && y >= 0 && x < a.length && y < a[0].length);
}

private static boolean allRotten(int[][] a) {
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < a[0].length; j++) {
if (a[i][j] == 1)
return false;
}
}
return true;
}

public static void main(String[] args) {
int[][] a = new int[][] { { 1, 1, 2, 2 }, { 1, 2, 2, 2 }, { 2, 2, 0, 0 }, { 2, 2, 0, 1 } };
System.out.println(getTime(a));
}

}

class Cell {

``````int x;
int y;

public Cell(int x, int y) {
this.x = x;
this.y = y;
}
``````

}

• I'm not sure what @aceofspades means by maximum time or minimum time (in the title it says maximum time and in the description it says we have to determine the minimum time). What I understand is that find the time that till all fresh oranges get rotten (if possible).

Complexity is O(M x N) because we only visit each cell once. Fresh oranges that got infected will be visited twice.

``````int timeToRot = 0;
public void problemTimeToRotOrange() {
int[][] farm = new int[][] {{1, 1, 1, 1, 0},
{0, 1, 0, 1, 1},
{2, 1, 1, 0, 2},
{2, 1, 1, 0, 0}};
//		int[][] farm = new int[][] {{1, 0, 1, 1, 0},
//									{0, 1, 0, 1, 1},
//									{2, 1, 1, 0, 2},
//									{2, 1, 1, 0, 0}};
timeToRotFarm(farm);
//		for(int i = 0; i < farm.length; i++) {
//			for(int j = 0; j < farm[0].length; j++)
//				System.out.print(farm[i][j] + " ");
//			System.out.println();
//		}
for(int i = 0; i < farm.length; i++) {
for(int j = 0; j < farm[0].length; j++) {
if(farm[i][j] == 1) {
timeToRot = -1;
break;
}
}
}
System.out.println(timeToRot);
}

private void timeToRotFarm(int[][] farm) {
boolean[][] visited = new boolean[farm.length][farm[0].length];
for(int i = 0; i < farm.length; i++) {
for(int j = 0; j < farm[0].length; j++) {
if(farm[i][j] == 2)
rotCrop(farm, i, j, visited);
}
}
}

private void rotCrop(int[][] farm, int i, int j, boolean[][] visited) {
if(i < 0 || i == farm.length || j < 0 || j == farm[0].length || farm[i][j] == 0 || visited[i][j])
return;
if(farm[i][j] == 2) {
visited[i][j] = true;
// move north
rotCrop(farm, i - 1, j, visited);
// move east
rotCrop(farm, i, j + 1, visited);
// move south
rotCrop(farm, i + 1, j, visited);
// move west
rotCrop(farm, i, j - 1, visited);
return;
} else if(farm[i][j] == 1){
// farm[i][j] = 1, it's fresh so infect it
farm[i][j] = 2;
timeToRot++;
rotCrop(farm, i, j, visited);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.