class Solution {

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

    public int[][] updateMatrix(int[][] mat) {
        int r = mat.length;
        int c = mat[0].length;

        int MAX_VALUE = r*c; //treating mat as visted arrays as well
        Queue<Integer> queue = new LinkedList<>();

        for(int i = 0; i < r; i ++){
            for(int j = 0; j < c; j ++){
                if(mat[i][j] == 0){
                    //add to queue
                    int n = i*c + j;
                    queue.add(n);
                }else{
                    mat[i][j] = MAX_VALUE;
                }
            }
        }

        //BFS traversal from multisource
        while(!queue.isEmpty()){
            int sz = queue.size();
            while(sz -- > 0){
                int cn = queue.poll();
                int cnr = cn / c;
                int cnc = cn % c;

                for(int d = 0; d < 4; d ++){
                    int nr = cnr + dir[d][0];
                    int nc = cnc + dir[d][1];
                    int nn = nr*c + nc;

                    //boundary check
                    if(nr >= 0 && nc >=0 && nr < r && nc < c){
                        //updating minimum steps to reach mat[nr][nc]
                        if(mat[nr][nc] > mat[cnr][cnc] + 1){
                            queue.add(nn);
                            mat[nr][nc] = mat[cnr][cnc] + 1;
                        }
                    }
                }
            }
        }

        return mat;
    }
}