Advertisement
rishu110067

Untitled

Jan 21st, 2022
1,093
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.     public static int getNeighbor(int row, int col, List<List<Integer>> matrix, int[][] index){
  3.         int[][] DIR = {{1, 0}, {-1, 0}, {0 , -1}, {0, 1}};
  4.         int min = Integer.MAX_VALUE;
  5.         int minRow = 0;
  6.         int minCol = 0;
  7.         for(int[] dir: DIR){
  8.             int nRow = row + dir[0];
  9.             int nCol = col + dir[1];
  10.             if(nRow>=0 && nCol>= 0 && nRow < matrix.size() && nCol<matrix.get(0).size()){
  11.                 if(matrix.get(nRow).get(nCol) < min){
  12.                     min = matrix.get(nRow).get(nCol);
  13.                     minRow = nRow;
  14.                     minCol = nCol;
  15.                 }
  16.             }
  17.         }
  18.  
  19.         if(min <= matrix.get(row).get(col)){
  20.             return index[minRow][minCol];
  21.         }
  22.         return -1;
  23.     }
  24.  
  25.     public static int find(int node, Map<Integer, Integer> parent){
  26.        
  27.         Integer curr = node;
  28.         while(parent.get(curr) != curr){
  29.             parent.put(curr, parent.get(parent.get(curr))); // path compression
  30.             curr = parent.get(curr);
  31.         }
  32.         return curr;
  33.     }
  34.  
  35.     public static void union(int u, int v, Map<Integer, Integer> parent, Map<Integer, Integer> size, int[][] index){
  36.  
  37.         int rootu = find(u, parent);
  38.         int rootv = find(v, parent);
  39.         if(size.get(rootu) <= size.get(rootv)){
  40.             parent.put(rootu, rootv);
  41.             size.put(rootv, size.get(rootv) + size.get(rootu));
  42.             size.put(rootu, 0);
  43.         }
  44.         else { // size.get(rootv) < size.get(rootu)
  45.             parent.put(rootv, rootu);
  46.             size.put(rootu, size.get(rootv) + size.get(rootu));
  47.             size.put(rootv, 0);
  48.         }
  49.     }
  50.    
  51.     public static List<Integer> find_basins(List<List<Integer>> matrix) {
  52.         //Write your code here
  53.         /**
  54.          * Steps:
  55.          * - implement Kruskal's algorithm
  56.          *  - for each element on the matrix figure out its neigbors's minimum value
  57.          *  - find the neighbors's element and do a union
  58.          */
  59.  
  60.         Map<Integer, Integer> parent = new HashMap<>();
  61.         Map<Integer, Integer> size = new HashMap<>();
  62.         int[][] index = new int[matrix.size()][matrix.get(0).size()];
  63.         List<Integer> results = new ArrayList<>();
  64.  
  65.         // initialize the parent and size maps
  66.         for(int row=0; row<matrix.size(); row++) {
  67.             for (int col = 0; col < matrix.get(0).size(); col++) {
  68.                 int idx = row * matrix.get(0).size() + col;
  69.                 index[row][col] = idx;
  70.                 parent.put(idx, idx);
  71.                 size.put(idx, 1);
  72.             }
  73.         }
  74.  
  75.         // start going through each cell and performing union
  76.         for(int row=0; row<matrix.size(); row++){
  77.             for(int col=0; col<matrix.get(0).size(); col++){
  78.                 int neighbor = getNeighbor(row, col, matrix, index);
  79.                 if(neighbor != -1){ // perform union
  80.                     union(index[row][col], neighbor, parent, size, index);
  81.                 }
  82.             }
  83.         }
  84.  
  85.         // construct the results
  86.         for(int i = 0; i <  matrix.size()*matrix.get(0).size(); i++){
  87.             if(i == parent.get(i)){
  88.                 results.add(size.get(i));
  89.             }
  90.         }
  91.         Collections.sort(results);
  92.         return results;
  93.     }
  94. }
  95.  
  96.  
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement