Q33 Minimize Hamming Distance After Swap Operations - LeetCode 1722

class Solution {
    public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
        /* Q33 graph playlist
        */
        int n = source.length;
        DSU main =  new DSU(n);

        //grouping swaps
        for(int swap[] : allowedSwaps){
            int a = swap[0] , b = swap[1];
            
            main.union(a,b , main.parent , main.rank);
        }

        /* making a HM<Integer , HM<Int,int>> to store after swapping what values can 
        the swap_index hold in the source array 
        */

        HashMap<Integer,HashMap<Integer,Integer>> map = new HashMap<>();
        
        //traversing parent array and storing values for parent swap_index
        for(int i = 0 ;i < n ; i++){
            int par = main.find(main.parent[i] , main.parent);

            if(map.containsKey(par) == false)
            map.put(par , new HashMap<>());
            
            //taking out hashmap against swap_index
            HashMap<Integer,Integer> temp = map.get(par);
            
            //updating value - frequenccy
            temp.put(source[i] , temp.getOrDefault(source[i] , 0) +1);

            map.put(par , temp);
        }
    
        //traversing target array and making answer
        int ans = 0;

        for(int i = 0 ;i < n ; i++){
            int root = main.find(i , main.parent);     //parent of index i
            int val = target[i];

            HashMap<Integer,Integer> temp = map.get(root);

            //if no value exist against swap_index 
            if(temp.containsKey(val) == false){
                ans++;
                continue;
            }

            //if frequency of value against swap_index <=0
            if(temp.get(val) <= 0 )
            ans++;

            //updating val -> frequency and updating orignal map
            temp.put(val , temp.get(val) -1);
            map.put(root , temp);
           
        }

        return ans;
    }
    public static class DSU{
        static int parent[] , rank[];

        DSU(int n ){
            parent = new int[n];
            rank = new int[n];

            for(int i = 0 ;i < n ; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int child , int parent[]) {
            //if it is its own parent
            if(parent[child] == child){
                return parent[child];
            }

            int temp  = find(parent[child] , parent);    //optimization 1 (path compression)
            parent[child] = temp;

            return temp;
        }

        //x and y are childrens
        public boolean union(int x , int y , int parent[] , int rank[]){
            //finding leaders
            int lx = find(x , parent);
            int ly = find(y , parent);
            
            //combining based on ranks
            if(lx != ly){

                if(rank[lx] > rank[ly]){
                    parent[ly] = lx;
                }
                else if(rank[lx] < rank[ly]){
                    parent[lx] = ly;
                }

                else{
                    parent[lx] = ly;
                    rank[ly] ++ ;
                }
                return true;
            }
            return false;
        }
        
    }

}