Union-Find — Min Cost to Connect All Points
↗ LeetCode: Min Cost to Connect All Points · Medium · pattern chapter →
Asked atAmazonMeta
Given 2D points, connect all with min total Manhattan distance.
Example 1 — points=[[0,0],[2,2],[3,10],[5,2],[7,0]] → 20Example 2 — points=[[3,12],[-2,5],[-4,1]] → 18
Constraints — 1 ≤ n ≤ 1000. Brute enumerates spanning trees — dies past n=12. Prim/Kruskal with Union-Find is O(n² log n) = 10⁶ ops at n=10³ = <5 min at scale.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Kruskal on all pairs
Build O(n²) edges; sort; UF. O(n² log n) time; works for n=1000.
java
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++)
edges.add(new int[]{i, j, Math.abs(points[i][0]-points[j][0]) + Math.abs(points[i][1]-points[j][1])});
edges.sort((a, b) -> a[2] - b[2]);
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int cost = 0, cnt = 0;
for (int[] e : edges) {
int ra = find(parent, e[0]), rb = find(parent, e[1]);
if (ra == rb) continue;
parent[ra] = rb; cost += e[2];
if (++cnt == n - 1) break;
}
return cost;
}
int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }Execution Trace
Step 1 / 3Initialize scan.
Approach 2 — Prim with priority queue (canonical for dense)
Insight. Start at any node; repeatedly add closest unvisited. O(n²) unvisited scans without heap, or O(E log V) with heap.
Complexity — Time O(n² log n) heap-based; O(n²) without heap; Space O(n²) for edges.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Kruskal all pairs | O(n² log n) | O(n²) | works |
| Prim + heap | O(n² log n) | O(n²) | canonical |
| Prim without heap | O(n²) | O(n) | best for dense |
When to use which
- Complete graph (dense) → Prim without heap.
- Sparse edges → Kruskal.
- "Second best MST" → replace each edge with next-cheapest non-MST option.
AI Study CompanionBeta
Related problems
- Connecting Cities With Minimum Cost
- Optimize Water Distribution
- Find Critical/Pseudo-Critical MST Edges
Was this page helpful?