class Solution {
    public int[][] matrixRankTransform(int[][] matrix) {
        /* Q32 graph playlist , 
        1) we will sort the array to get smaller nos. first to give them rank so we make a pair class
        to store the orignal positions of elements

        2)we sort the pair array
        
        3) we make a public rows and cols array which will store the max 

        4)we group same elements in an arraylist and process them together , as same elements in a row
        or coloumn will have same rank , so we will use DSU concept to group them by having same 
        parent
        */
        int m = matrix.length , n = matrix[0].length;
        pair arr[] = new pair[m*n];
        
        //making pair array 
        int k = 0 ;
        for(int i = 0 ;i < m ; i++){
            for(int j = 0 ;j < n ;j++){
                arr[k] = new pair(matrix[i][j] , i , j);
                k++;
            }
        }

        Arrays.sort(arr);
        
        //initialising public rows and cols
        rows = new int[m];
        cols = new int[n];

        //grouping and processing same elements together
        ArrayList<pair> group = new ArrayList<>();
        int last = Integer.MIN_VALUE;

        for(int i =0 ; i < m*n ; i++){
            int val = arr[i].point;
            
            //if new val , send last group to process ranks
            if(val != last){
                process(group , matrix);
                last = val;
                group = new ArrayList<>();
            }
            group.add(arr[i]);
        }

        //if last group is left in the arraylist it will get processed here
        process(group , matrix);
        
        //we have done all the changes in matrix itself
        return matrix;
    }
    
    //for storing current maximum rank in respective row and col
    int rows[];
    int cols[];


    //will return parent , final parent will still have -1 
    public int findparent(int u , int[] parent){
        if(parent[u] < 0){
            return u;           //as in parent array we initiliaze parent[i] = i;
        }
        int temp = findparent(parent[u] , parent);
        parent[u] = temp;

        return temp;
    }

    public void process(ArrayList<pair> group , int[][] matrix){
        int m = matrix.length , n = matrix[0].length;

        //defining parent array for both row and coloumn in 1 array only
        int parent[] = new int[m+n]; 
        Arrays.fill(parent , -1);

        /* when p1!=p2 we can group either p1 to p2 or p2 to p1 , therefore we group p2 to p1 
        now parent[p1] still has -1 , so we will store maximum rank of this group int parent[p1] 
        but in negative (so findparent still works properly)
        */
        for(pair element : group){
            int x = element.x , y = element.y ;

            //finding parents in row parent array and col parent array
            int p1 = findparent(x , parent);
            int p2 = findparent(y+m , parent);
            
            //grouping
            if(p1 != p2){
                /* finding maxrank of this group  , maxrank will be previous maxrank +1 , as all value
                are being stored in negative we find maxrank -1 and we find math.min of all 
                
                -> but in rows and cols values are stored in +ve only
                */
                int maxRank = Math.min(parent[p1] , Math.min(parent[p2] ,-Math.max(rows[x],cols[y])-1));
                
                //storing max rank in p1 but in negative
                parent[p1] = maxRank;

                //grouping p2 to p1
                parent[p2] = p1;
                
            }  
        }
        //updating matrix
        for(pair element : group){
            int x = element.x , y = element.y , point = element.point;

            //p1 & p2 already grouped now , so find rank 
            int p1 = findparent(x , parent);
            int rank = -parent[p1];

            //update rank
            rows[x] = rank;
            cols[y] = rank;
            
            matrix[x][y] = rank;
        } 
    }
    public class pair implements Comparable<pair>{
        int point , x , y;

        pair(){}

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

        //ascending order
        public int compareTo(pair o){
            return this.point - o.point;
        }
    }
}