Min Cost to Connect All Points
You are given an array of points where:
points[i] = [xi, yi]
represents a point on a 2D plane.
The cost of connecting two points is their Manhattan distance:
|x1 - x2| + |y1 - y2|
Return the minimum total cost required to connect all points.
All points must be connected, and there must be exactly one path between any two points.
Example
points =
[
[0,0],
[2,2],
[3,10],
[5,2],
[7,0]
]
The minimum cost is:
20
Main Idea
This is a Minimum Spanning Tree (MST) problem.
Every point can be considered a node, and the Manhattan distance between two points is the edge weight.
We need to connect all points with the minimum possible total edge weight.
Two common approaches are:
Prim's Algorithm
Kruskal's Algorithm
For this problem, Prim's Algorithm is simple and efficient.
Prim's Algorithm
- Start from any point.
- Find the minimum-cost edge connecting the current MST to an unvisited point.
- Add that point to the MST.
- Update the minimum distance for the remaining points.
- Continue until every point is included.
Example 1
Input
5 0 0 2 2 3 10 5 2 7 0
Output
20
Explanation
One minimum-cost connection is:
[0,0] → [2,2] = 4
[2,2] → [5,2] = 3
[5,2] → [7,0] = 4
[2,2] → [3,10] = 9
Total:
4 + 3 + 4 + 9 = 20
Therefore, the minimum cost is:
20
Example 2
Input
3 3 12 -2 5 -4 1
Output
18
Explanation
The Manhattan distances are:
[3,12] → [-2,5] = 12
[-2,5] → [-4,1] = 6
So:
12 + 6 = 18
Therefore, the minimum total cost is:
18
Constraints
Hints:
Hint 1
Think of every point as a node.
The cost between two points is their Manhattan distance.
Hint 2
You need to connect all nodes with minimum total cost.
This is exactly the definition of a Minimum Spanning Tree.
Author & Technical Reviewer
Technically reviewed by: ExamAdda Technical Review Team
Technical Reviewers, ExamAdda
Software engineers at ExamAdda who check every article's definitions, complexity claims and code examples before and after publishing.
Published
Aug 16, 2026
Last updated
Aug 17, 2026
Content Verification Methodology
Definitions and complexity claims were checked against authoritative computer-science references. Code examples were compiled and tested with standard, boundary and edge-case inputs.
Expected Output