Union-Find — Connecting Cities With Minimum Cost
↗ LeetCode: Connecting Cities With Minimum Cost · Medium · pattern chapter →
Asked atAmazonGoogleMeta
Given n cities and connections[i] = [a, b, cost], return the minimum cost to make all connected. -1 if impossible.
Example 1 — n=3, connections=[[1,2,5],[1,3,6],[2,3,1]] → 6 (pick [2,3,1] and [1,2,5]) Example 2 — n=4, connections=[[1,2,3],[3,4,4]] → -1
Constraints — 1 ≤ n ≤ 10⁴. Brute checks every spanning tree — O(n^(n-2)) via Cayley (dies past n=12). Kruskal + Union-Find is O(E log E) = ~10⁶ ops at E=10⁴.
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 — Try all spanning trees
Exponential. Baseline.
Approach 2 — Kruskal MST (canonical)
Insight. Sort edges by cost; process ascending. Add if it unions two components; skip otherwise. Stop when we have n-1 edges. If fewer, return -1.
java
int minimumCost(int n, int[][] connections) {
Arrays.sort(connections, (a, b) -> a[2] - b[2]);
int[] parent = new int[n + 1];
for (int i = 0; i <= n; i++) parent[i] = i;
int cost = 0, edges = 0;
for (int[] e : connections) {
int ra = find(parent, e[0]), rb = find(parent, e[1]);
if (ra == rb) continue;
parent[ra] = rb;
cost += e[2];
if (++edges == n - 1) return cost;
}
return -1;
}
int find(int[] p, int x) { return p[x] == x ? x : (p[x] = find(p, p[x])); }Execution Trace
Complexity — Time O(E log E); Space O(n).
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| Enumerate ST | exponential | O(n) | baseline |
| Kruskal + UF | O(E log E) | O(n) | canonical |
When to use which
- Sparse graph → Kruskal.
- Dense graph → Prim + heap: O(E + V log V).
- "Second-best MST" → replace each MST edge with best non-MST alternative.
AI Study CompanionBeta
Related problems
Was this page helpful?
📚 Related problems