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;
        }
    }
}