28 · Union-Find & Minimum Spanning Trees
#1584 Min Cost to Connect All Points
the problem
In plain words
Given points on a 2D plane, the cost to connect two points is their Manhattan distance |x₁ − x₂| + |y₁ − y₂|. Return the minimum cost to connect all points so that every pair has exactly one simple path between them.
in points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
out 20
in points = [[3,12],[-2,5],[-4,1]]
out 18
- 1 ≤ points.length ≤ 1000
- -10⁶ ≤ xᵢ, yᵢ ≤ 10⁶
- All points are distinct
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternMinimum spanning tree (Kruskal / Prim)
"Exactly one path between every pair" = a tree; minimum cost = minimum spanning tree of the complete graph. With every pair connected, E ≈ n²/2, so array-based Prim (O(n²)) beats anything that builds the edge list.
solutions
From brute force to optimal
Generate every pair as an edge, sort, and run Kruskal with a DSU.
- Build all n(n−1)/2 edges {cost, i, j}.
- Sort by cost.
- Union until n − 1 edges are taken.
Sorting n²/2 edges: O(n² · log n²) = O(n² log n).
The full edge list (~500 000 entries for n = 1000).
class Solution { private int[] parent; private int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); return parent[x]; } public int minCostConnectPoints(int[][] points) { int n = points.length; List<int[]> edges = new ArrayList<>(); // {cost, i, j} for every pair for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) edges.add(new int[] {dist(points, i, j), i, j}); edges.sort(Comparator.comparingInt(e -> e[0])); parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i; int cost = 0, used = 0; for (int[] e : edges) { int ra = find(e[1]), rb = find(e[2]); if (ra == rb) continue; parent[ra] = rb; cost += e[0]; if (++used == n - 1) break; } return cost; } private int dist(int[][] p, int i, int j) { return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]); // Manhattan distance }}Grow one tree; push the distance to every outside point; skip stale entries.
- Start from point 0.
- Poll the cheapest entry; skip if already in the tree.
- Add it and push its distance to every outside point.
Up to n² pushes, each O(log n²) = O(log n).
The heap can hold up to ~n²/2 stale entries.
class Solution { public int minCostConnectPoints(int[][] points) { int n = points.length; boolean[] inTree = new boolean[n]; PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); // {cost, node} pq.offer(new int[] {0, 0}); int cost = 0, added = 0; while (added < n) { int[] top = pq.poll(); int u = top[1]; if (inTree[u]) continue; // stale entry inTree[u] = true; cost += top[0]; added++; for (int v = 0; v < n; v++) { if (!inTree[v]) pq.offer(new int[] {dist(points, u, v), v}); } } return cost; } private int dist(int[][] p, int i, int j) { return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]); // Manhattan distance }}Keep the cheapest known link for every outside point; each round scan for the minimum, add it, and relax the others.
- best[0] = 0, others ∞.
- n rounds: pick the outside point u with the smallest best[u]; cost += best[u].
- For every outside v, best[v] = min(best[v], dist(u, v)).
n rounds × (n to pick + n to relax). No sorting, no heap.
Two arrays of size n; distances are computed on the fly.
class Solution { public int minCostConnectPoints(int[][] points) { int n = points.length; int[] best = new int[n]; // cheapest cost to connect each point to the tree so far boolean[] inTree = new boolean[n]; Arrays.fill(best, Integer.MAX_VALUE); best[0] = 0; int cost = 0; for (int round = 0; round < n; round++) { int u = -1; for (int v = 0; v < n; v++) { // closest point not yet in the tree if (!inTree[v] && (u == -1 || best[v] < best[u])) u = v; } inTree[u] = true; cost += best[u]; for (int v = 0; v < n; v++) { // can u offer a cheaper link to anyone? if (!inTree[v]) { int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]); if (d < best[v]) best[v] = d; } } } return cost; }}Dry run
in the room
How to say it in the interview
talk track
- Translate the wording: "exactly one path between every pair" means a tree; "minimum cost" means MST.
- Note the graph is complete (E ≈ n²/2). That makes O(V²) Prim optimal — mention that Kruskal works but stores and sorts ~500k edges.
traps
- Using Euclidean distance — this problem uses Manhattan, |x₁ − x₂| + |y₁ − y₂|.
- Dense Prim: forgetting to mark the picked point as in the tree, so it is picked again.
- Heap Prim: not skipping stale entries for points already in the tree, so their cost is added twice.
what they ask next
Follow-ups
Connecting Cities With Minimum Cost (LC 1135, Premium)?
Same MST question with an explicit edge list — Kruskal is the natural choice; return -1 if fewer than n − 1 edges get used.
Can Manhattan MST be faster than O(n²)?
Yes: only O(n) candidate edges (nearest neighbour in each of 8 octants) are needed, giving O(n log n) — far beyond interview scope.
before you submit
Edge cases to test
- One point → cost 0.
- Two points at opposite corners (±10⁶) → 4,000,000: still fits in an
int. - Points on one line: the MST is just the line, cost = max − min.
- Many equal distances: several MSTs exist, but they all cost the same.
practise next
Similar problems
- #1489Find Critical and Pseudo-Critical Edges in Minimum Spanning TreeHardin Union-Find & MST
- #1631Path With Minimum EffortMediumin Shortest Paths
- #743Network Delay TimeMediumin Shortest Paths