class Solution {
    public int maxDistance(int[][] grid) {
        /* Q-6 of graph playlist , we make a pair class with row , col , distance  , first 
        add all 1s to the q with distance 0 , fire bfs , encountering a 0 we change it to 1
        and make its distance + 1 
        
        we keep a max variable also while we fire bfs and store max distance along the way
        
        */
        int m = grid.length , n = grid[0].length ;
        LinkedList<pair> q = new LinkedList<>();
        
        //adding all 1s to q
        int water = 0 , land = 0;
        for(int i = 0 ;i < m ;i++){
            for(int j = 0 ; j < n ;j++){
                if(grid[i][j] == 1){
                    land ++;
                    q.addLast(new pair(i, j , 0));
                }
                

                else
                water++;
            }
        }
        
        //edge case
        if(water == 0 || land == 0)  return -1;

    
        int max = -1;
        //firing bfs
        while(q.size() > 0){
            pair rem = q.removeFirst();
            int row = rem.x ; int col = rem.y ; int dist = rem.dist;

            max = Math.max(dist , max);

            for(int i =0 ;i < 4 ; i++){
                int rowdash = row + dir[i][0];
                int coldash = col + dir[i][1];

                //if valid water cell change it to land cell and make its dist + 1
                if(rowdash >=0 && coldash >=0 && rowdash < m && coldash < n &&
                grid[rowdash][coldash] == 0){
                    grid[rowdash][coldash] = 1;
                    q.add(new pair(rowdash , coldash , dist + 1));
                }
            }
        }

        return max;
    }

    public int dir [][] = {{0,1},{1,0},{-1,0},{0,-1}};

    public class pair{
        int x , y , dist;

        pair(int x , int y , int dist){
            this.x = x; this.y = y ; this.dist = dist;
        }
    }
}