class Solution {
public int orangesRotting(int[][] grid) {
/* Q5 of graph playlist , we make a pair class with row , col , time , we add all
2's in the q and fire bfs , and increase the time of the next oranges as that
will be the time it takes for them to become rotten and then we also add those
oranges in the queue
*/
LinkedList<pair> q = new LinkedList<>();
int m = grid.length , n = grid[0].length;
//counting fresh oranges and adding rottens to queue
int fresh = 0 ;
for(int i = 0 ;i < m ; i++){
for(int j = 0 ; j < n ; j++){
if(grid[i][j] == 2)
q.addLast(new pair(i , j , 0));
else if(grid[i][j] == 1)
fresh ++;
}
}
int time = 0;
//firing bfs
while(q.size() > 0){
pair rem = q.removeFirst();
time = rem.time;
int row = rem.x ;
int col = rem.y;
//adding next rotten oranges and updating their time
for(int i = 0 ;i < 4 ; i++){
int rowdash = row + dir[i][0];
int coldash = col + dir[i][1];
if(rowdash >= 0 && coldash >= 0 && rowdash < m && coldash < n &&
grid[rowdash][coldash] == 1){
grid[rowdash][coldash] = 2;
fresh --;
q.addLast(new pair(rowdash,coldash , time + 1));
}
}
}
System.out.println(time);
return fresh == 0 ? time : -1;
}
//directions and pair class with row , col , time
public int[][] dir = {{0,1} , {1,0} , {-1,0} , {0,-1}};
public class pair{
int x , y , time;
pair(int x , int y ,int time){
this.x = x;
this.y = y;
this.time = time;
}
}
}
Comments