Q31 Regions Cut By Slashes - LeetCode 959

class Solution {
    public int regionsBySlashes(String[] grid) {
        /* Q31 graph  , DSU question
        1) convert n x n grid to n+1 x n+1 points on graph 
        2) convert 2d graph to 1d graph 
        3) connect boundaries and start answer with 1 as 1st region will be matrix itself
        4) figure out which type of slash connects which 2 points
        5) apply kruskal and check for cycle , if cycle exist increase region by 1
        */
        int n = grid.length;
        int dots = n+1;

        DSU temp = new DSU(dots * dots);

        //connecting boundaries point to 1 to form 1st region by matrix itself
        for(int i = 0 ;i < dots ; i++){
            for(int j = 0 ;j < dots ; j++){
                
                if(i == 0 || i == dots-1 || j==0 || j== dots-1){
                    //convert to cell no.
                    int cellno = i * dots + j;

                    // 0 and 0 will have same leader
                    temp.union(0 , cellno , DSU.parent , DSU.rank);
                }
                
            }
        }
        int ans = 1;

        //applying kruskal on grid
        for(int i = 0 ;i < grid.length ; i++){
            String str = grid[i];
            
            for(int j = 0 ;j < str.length(); j++){

                //(i+1 , j) && (i , j+1);
                if(str.charAt(j) == '/'){
                    int a = (i+1) * dots + j , b = i * dots + (j+1);

                    if(temp.union(a , b , temp.parent , temp.rank) == false)
                    ans++;
                }
                //(i , j) && (i+1 , j+1);
                else if(str.charAt(j) == '\\'){
                    int a = (i) * dots + j , b = (i+1) * dots + (j+1);

                    if(temp.union(a , b , temp.parent , temp.rank) == false)
                    ans++;

                    // j++;    //as its given for / we have '//' therefore we skip 1 char
                }
            }
        }
        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;
        }
        
    }

}