Problem Description
You are given an m x n grid where each cell can have one of three values:
- 0 representing an empty cell,
- 1 representing a fresh orange, or
- 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Solution
The rotting of oranges will start from every exiting rotten orange in the given matrix. So, we will need to start from all those positions and keep visiting its neighbours. While visiting the neighbours, we will need to keep a track of time when they rot. This will be 1 more than the cell from which it got rot. We can create a new matrix to keep a track of time to rot. This can also be used to check if that node/cell has been visited. The idea is basically to apply Multi Source BFS.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
class Solution {
public int orangesRotting(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
//Queue to add neighbours while visiting the nodes/cells
Queue<Pair> queue = new LinkedList<>();
//time array to track at what time a certain orange will be rotten
int[][] time = new int[n][m];
//initialize time to rot as -1 (not visited)
for(int i=0; i<n; i++){
Arrays.fill(time[i], -1);
}
//add rotten oranges in the queue and mark them visited
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
//if grid[i][j] is 2, that orange is rotten as per the problem
if(grid[i][j] == 2){
//add it to the queue
queue.add(new Pair(i, j));
//mark the time as 0 (marking visited)
//making it 0 will also help in calculating the time for neighboring oranges
time[i][j] = 0;
}
}
}
//variable to track the max time any fresh orange took to rot
int maxTime = 0;
//direction helper to visit cells towards top, bottom, left, right
int[] x = {0, 0, 1, -1};
int[] y = {1, -1, 0, 0};
//while queue is not empty, keep visiting the neighbours of rotten oranges and make then rot
//each time, update the time to rot in the time matrix
while(!queue.isEmpty()){
//get the rotten orange from the queue
Pair p = queue.poll();
//get it's ith and jth indices
int i = p.x;
int j = p.y;
//visit the neighboring nodes/cells
for(int k=0; k<4; k++){
//calculate the next indicates to be visited
int a = i+x[k];
int b = j+y[k];
//check if they are within the bounds
//they have not been visited -> time[a][b] == -1
//and they are not empty -> grid[a][b] != 0
if(a>=0 && b>=0 && a<n && b<m && time[a][b] == -1 && grid[a][b] != 0){
//add the orange to queue so that its neighbours can be visited
queue.add(new Pair(a, b));
//mark the time to rot (it will be 1 more than the time to rot from the previous cell)
time[a][b] = time[i][j] + 1;
//update maxTime to rot
maxTime = Math.max(maxTime, time[a][b]);
}
}
}
//There is a chance that not all the oranges have been rotten, in which case we can return -1
if(allRotted(grid, time)){
return maxTime;
}else{
return -1;
}
}
public boolean allRotted(int[][] grid, int[][] time){
for(int i=0; i<time.length; i++){
for(int j=0; j<time[0].length; j++){
if(grid[i][j] == 1 && time[i][j] == -1) return false;
}
}
return true;
}
}
class Pair{
int x;
int y;
Pair(int x, int y){
this.x = x;
this.y = y;
}
}
Small Optimization
We can maintain a few variables to count:
- Number of fresh oranges initially
- Number of oranges which were rotten (while doing BFS)
- Time needed to rot all oranges (we can keep increasing it if we find that the time taken to rot some orange is higher)
Using the above variables, we don’t need to traverse the entire matrix to check if there were any remaining oranges.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public int orangesRotting(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] time = new int[n][m];
Queue<Pair> q = new LinkedList<>();
int freshOrange = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(grid[i][j] == 2){
time[i][j] = 0;
q.add(new Pair(i,j));
continue;
}
if(grid[i][j] == 1){
freshOrange++;
}
time[i][j] = -1;
}
}
int timeNeeded = 0;
int countOrangeRotted = 0;
while(!q.isEmpty()){
Pair p = q.poll();
int[] x = {0, 0, 1, -1};
int[] y = {1, -1, 0, 0};
for(int k=0; k<4; k++){
int x2 = p.x + x[k];
int y2 = p.y + y[k];
if(x2 >=0 && y2 >=0 && x2<n && y2<m && time[x2][y2] == -1 && grid[x2][y2] != 2 && grid[x2][y2] != 0){
countOrangeRotted++;
grid[x2][y2] = 2;
q.add(new Pair(x2, y2));
time[x2][y2] = time[p.x][p.y] + 1;
timeNeeded = Math.max(timeNeeded, time[x2][y2]);
}
}
}
if(freshOrange > countOrangeRotted) return -1;
return timeNeeded;
}
}
class Pair{
int x;
int y;
Pair(int x, int y){
this.x = x;
this.y = y;
}
}