Update Min Cost to Connect All Points.java

varunu28 · web-flow · commit 76f32c6f4fd8 · 2023-09-15T09:28:06.000-07:00
diff --git a/Medium/Min Cost to Connect All Points.java b/Medium/Min Cost to Connect All Points.java
@@ -1,80 +1,64 @@
 class Solution {
-  public int minCostConnectPoints(int[][] points) {
-    int n = points.length;
-    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>((x, y) -> x.cost - y.cost);
-    UnionFind unionFind = new UnionFind(n);
-    for (int i = 0; i < n; i++) {
-      int[] coordinate = points[i];
-      for (int j = i + 1; j < n; j++) {
-        int[] secondCoordinate = points[j];
-        int cost = Math.abs(coordinate[0] - secondCoordinate[0]) + Math.abs(coordinate[1] - secondCoordinate[1]);
-        Edge edge = new Edge(i, j, cost);
-        priorityQueue.add(edge);
-      }
-    }
-    int minimumCost = 0;
-    int totalEdges = n - 1;
-    while (!priorityQueue.isEmpty() && totalEdges > 0) {
-      Edge edge = priorityQueue.poll();
-      if (!unionFind.connected(edge.pointOne, edge.pointTwo)) {
-        unionFind.union(edge.pointOne, edge.pointTwo);
-        minimumCost += edge.cost;
-        totalEdges--;
-      }
-    }
-    return minimumCost;
-  }
-
-  private static class Edge {
-    int pointOne;
-    int pointTwo;
-    int cost;
-
-    public Edge(int pointOne, int pointTwo, int cost) {
-      this.pointOne = pointOne;
-      this.pointTwo = pointTwo;
-      this.cost = cost;
+    public int minCostConnectPoints(int[][] points) {
+        int n = points.length;
+        List<int[]> edges = new ArrayList<>();
+        for (int i = 0; i < n; i++) {
+            for (int j = i + 1; j < n; j++) {
+                int weight = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
+                int[] curr = {weight, i, j};
+                edges.add(curr);
+            }
+        }
+        Collections.sort(edges, Comparator.comparingInt(a -> a[0]));
+        UnionFind unionFind = new UnionFind(n);
+        int minCost = 0;
+        int edgeUsedCount = 0;
+        for (int i = 0; i < edges.size() && edgeUsedCount < n - 1; i++) {
+            int nodeOne = edges.get(i)[1];
+            int nodeTwo = edges.get(i)[2];
+            int weight = edges.get(i)[0];
+            if (unionFind.union(nodeOne, nodeTwo)) {
+                minCost += weight;
+                edgeUsedCount++;
+            }
+        }
+        return minCost;
     }
-  }
-
-  private static class UnionFind {
 
-    private final int[] root;
-    private final int[] rank;
+    private static class UnionFind {
+        private final int[] group;
+        private final int[] rank;
 
-    public UnionFind(int size) {
-      this.root = new int[size];
-      this.rank = new int[size];
-      for (int i = 0; i < size; i++) {
-        this.root[i] = i;
-        this.rank[i] = 1;
-      }
-    }
-
-    public void union(int nodeOne, int nodeTwo) {
-      int rootOne = find(nodeOne);
-      int rootTwo = find(nodeTwo);
-      if (rootOne != rootTwo) {
-        if (this.rank[rootOne] > this.rank[rootTwo]) {
-          this.root[rootTwo] = rootOne;
-        } else if (this.rank[rootOne] < this.rank[rootTwo]) {
-          this.root[rootOne] = rootTwo;
-        } else {
-          this.root[rootTwo] = rootOne;
-          this.rank[rootOne]++;
+        public UnionFind(int n) {
+            this.group = new int[n];
+            this.rank = new int[n];
+            for (int i = 0; i < n; i++) {
+                this.group[i] = i;
+            }
         }
-      }
-    }
 
-    public int find(int node) {
-      if (node == root[node]) {
-        return node;
-      }
-      return root[node] = find(root[node]);
-    }
+        public int find(int node) {
+            if (group[node] != node) {
+                group[node] = find(group[node]);
+            }
+            return group[node];
+        }
 
-    public boolean connected(int nodeOne, int nodeTwo) {
-      return find(nodeOne) == find(nodeTwo);
+        public boolean union(int nodeOne, int nodeTwo) {
+            int groupOne = find(nodeOne);
+            int groupTwo = find(nodeTwo);
+            if (groupOne == groupTwo) {
+                return false;
+            }
+            if (rank[groupOne] > rank[groupTwo]) {
+                group[groupTwo] = groupOne;
+            } else if (rank[groupOne] < rank[groupTwo]) {
+                group[groupOne] = groupTwo;
+            } else {
+                group[groupOne] = groupTwo;
+                rank[groupTwo]++;
+            }
+            return true;
+        }
     }
-  }
 }
