Q32 Rank Transform of a Matrix - LeetCode 1632
Thu Jun 08 2023 15:20:01 GMT+0000 (Coordinated Universal Time)
Saved by @Ayush_dabas07
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; } } }
Comments