Min Cost to Connect All Points
Problem Statement
You are given n points on a 2D plane, where points[i] = [xi, yi]. The cost of connecting two points is the Manhattan distance between them: abs(xi - xj) + abs(yi - yj).
Return the minimum total cost needed to connect all points so that every point is reachable from every other point. You may choose any set of edges, but the final network must be connected.
Input
A 2D integer array points, where each entry is a coordinate pair [x, y].
Output
An integer: the minimum possible total Manhattan distance to connect all points.
Constraints
- •
1 <= points.length <= 1000 - •
-10^6 <= xi, yi <= 10^6 - •
All pairs (xi, yi) are distinct
Examples
Example 1
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
20Example 2
points = [[3,12],[-2,5],[-4,1]]
18Learning Objectives
- Recognise that connecting all points with minimum total edge cost is a **minimum spanning tree** problem.
- Understand why this graph is complete and dense even though the input only lists points.
- Compare Prim's dense-graph view with Kruskal's edge-sorting plus Union-Find view.
Intuition
The input does not hand you edges, but every pair of points can be connected. That means the hidden graph is complete: n vertices and roughly n squared possible edges, each weighted by Manhattan distance. We need the cheapest connected network over all vertices, which is exactly a minimum spanning tree.
Two MST mindsets solve it cleanly. Prim's algorithm grows one connected tree. At any moment, every outside point has a cheapest known edge into the tree; repeatedly add the outside point with the smallest such cost and relax distances from it. Because the graph is dense, the simple O(n squared) array version is often better than building a huge heap of all possible edges.
Kruskal's algorithm looks globally instead: generate every possible edge, sort by cost, and use Union-Find to accept only edges that connect two different components. It is very reusable, but here sorting O(n squared) edges is heavier than dense Prim.
Common mistakes
- ×Trying shortest-path algorithms like Dijkstra. We are not finding a path between two points; we are choosing a cheapest connected network.
- ×Building only nearby-looking edges. Manhattan distance does not let you safely ignore arbitrary pairs without a specialised geometric proof.
- ×Stopping Prim after n - 1 loop iterations instead of adding all n vertices. The first vertex contributes cost 0, so the loop naturally runs n times.
- ×In Kruskal, adding an edge before checking whether its endpoints are already in the same component, which creates cycles and overpays.
Algorithm Explanation
Prim: Treat the points as vertices of a complete weighted graph. Start from any point with connection cost 0. Maintain minDist[i], the cheapest edge currently known from point i into the growing tree. Repeatedly choose the unvisited point with the smallest minDist, add that cost to the answer, then update every remaining point using the Manhattan distance from the newly added point.
Kruskal: Generate all n(n - 1) / 2 edges with their Manhattan weights. Sort them ascending by weight. Scan the sorted list, unioning endpoints when they belong to different components. Every successful union adds one MST edge; stop after n - 1 accepted edges.
Solutions
Solution 1: Prim's algorithm (dense array scan)
Prefer this for this exact LeetCode problem. The graph is complete, so an O(n squared) scan avoids materialising and sorting O(n squared) edges.
Grow one tree from an arbitrary start. For every point outside the tree, keep only its cheapest edge into the tree, then repeatedly absorb the cheapest outside point.
Step-by-step
- Initialise minDist[0] = 0 and every other minDist to infinity.
- Repeat n times: choose the unvisited index with the smallest minDist, mark it inside the tree, and add minDist[index] to the total.
- For every still-unvisited point, compute its Manhattan distance to the newly added point and lower minDist if this new edge is cheaper.
- When all points are inside the tree, the accumulated total is the MST cost.
O(n^2)
O(n)
The complete graph is explored lazily; every chosen point relaxes distances to all other points.
Java implementation
Solution 2: Kruskal's algorithm with Union-Find
Use this when the edge list is already explicit, when you want the most general MST template, or when sorting edges is acceptable.
Generate every possible pair as a weighted edge, sort by cost, and let Union-Find prevent cycles while accepting the cheapest edges that merge components.
Step-by-step
- Build a list of edges [cost, u, v] for every pair of points.
- Sort the edge list by cost ascending.
- Scan edges from cheapest to most expensive. If union(u, v) succeeds, add the cost and count one chosen edge.
- Stop once n - 1 edges have been chosen, because a connected tree on n vertices has exactly n - 1 edges.
O(n^2 log n)
O(n^2)
There are O(n squared) candidate edges to store and sort; Union-Find operations are near constant amortised time.
Java implementation
Dry Run
Sample input
Prim trace for points = [[0,0],[2,2],[3,10],[5,2],[7,0]]. Points are labelled 0 through 4.
| Step | Point added | Cost added | Best outside costs after relax | Total |
|---|---|---|---|---|
| 0 | 0 = [0,0] | 0 | 1:4, 2:13, 3:7, 4:7 | 0 |
| 1 | 1 = [2,2] | 4 | 2:9, 3:3, 4:7 | 4 |
| 2 | 3 = [5,2] | 3 | 2:9, 4:4 | 7 |
| 3 | 4 = [7,0] | 4 | 2:9 | 11 |
| 4 | 2 = [3,10] | 9 | none | 20 |
Prim never needs to remember every edge. It only keeps the cheapest way each outside point can attach to the current tree. The chosen attachment costs are 0, 4, 3, 4, and 9, so the minimum total is 20.
Interview Tips
Say the phrase minimum spanning tree early. Then justify the algorithm choice from input shape: this is a dense complete graph created by points, not a sparse edge list. That makes O(n squared) Prim especially attractive. If you present Kruskal too, mention that it is correct but pays to generate and sort about n squared edges. Interviewers often reward that trade-off more than a memorised implementation.
Likely follow-ups
- Return the actual selected edges in the minimum spanning tree, not just the cost.
- What changes if the graph is sparse and the input already provides weighted edges?
- Can you solve a dynamic version where points are added one at a time?
- How would the answer change if distance were Euclidean instead of Manhattan?
Similar Problems
Key Takeaways
- Minimum cost to connect all vertices is the signature of an MST problem.
- For a complete graph over points, dense O(n squared) Prim is usually the cleanest optimal answer.
- Kruskal is the general edge-sorting MST template; Union-Find is what keeps it cycle-free.
- The first Prim vertex contributes cost 0; every later vertex pays its cheapest attachment into the tree.