Q11 01 Matrix - LeetCode 542

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        /* Q4 of graph playlist , add all zeroes to q and mark all 1 to -1 , fire bfs from 
        all zeroes to find nearest 1 and update distance of 1 
        */
        int m = mat.length , n = mat[0].length;

        LinkedList<pair> q = new LinkedList<>();

        //adding all zeroes to the q
        for(int i =0 ; i < m ; i++){
            for(int j = 0 ; j < n ;j++){
                if(mat[i][j] == 0)
                q.addLast(new pair(i , j));

                else
                mat[i][j] = -1; //marking the cell as unvisited
            }
        }

        //firing reverse bfs from zeroes to solve all 1's
        while(q.size()>0){
            pair rem = q.removeFirst();

            for(int i = 0 ;i < 4 ; i++){
                int rowdash = rem.x + dir[i][0];
                int coldash = rem.y + dir[i][1];

                //if valid cell
                if(rowdash >= 0 && coldash >= 0 && rowdash < m && coldash < n &&
                mat[rowdash][coldash] < 0){

                    //updating distance of the cell
                    mat[rowdash][coldash] = mat[rem.x][rem.y] + 1;
                    //adding it to q to solve further cells
                    q.addLast(new pair(rowdash , coldash));
                }
                
            }
        }

        return mat;

    }
    public int[][] dir = {{0,1},{1,0},{-1,0},{0,-1}};
    public class pair {
        int x , y;
        
        pair(int x , int y){
            this.x = x;
            this.y = y;
        }
    }
}