Min Cost to Connect All Points

Problem in Plain English

Every pair of points can be joined at their Manhattan distance. Return the cheapest total cost that links all points into one connected network.

Problem Statement

You are given points where points[i] = [xi, yi] is a point on the 2D plane. Joining points [xi, yi] and [xj, yj] costs their Manhattan distance |xi - xj| + |yi - yj|.

Return the minimum cost to connect all points, meaning the joined points form exactly one connected network with a single simple path between any two points.

Constraints

1 <= points.length <= 1000
-10^6 <= xi, yi <= 10^6
All (xi, yi) pairs are distinct.

Examples

Example 1

Input: points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20

Join (2,2) to (5,2) for 3, (0,0) to (2,2) for 4, (5,2) to (7,0) for 4, and (2,2) to (3,10) for 9, totalling 20.

Example 2

Input: points = [[3,12],[-2,5],[-4,1]]
Output: 18

Join (-4,1) to (-2,5) for 6 and (-2,5) to (3,12) for 12, totalling 18.

Example 3

Input: points = [[-1000000,1000000]]
Output: 0

One point is already connected. No link is needed, even when its coordinates are at their allowed extremes.

Example 4

Input: points = [[0,0],[1,0],[1,1],[0,1]]
Output: 3

Any three sides of this square form a tree, each costing 1. Taking all four sides would cost 4 and create a cycle; equal-cost choices can produce different trees with the same minimum total.

Intuition

The network needs n - 1 links without cycles: adding a cycle creates two simple paths between some points and adds unnecessary positive cost. Treat each point as a vertex and each Manhattan distance as an edge weight. Example 1 connects points 0, 1, 3 and 4 for 11, then attaches point 2 for 9. The goal is a minimum spanning tree, which minimizes the sum of chosen links rather than the distance from one source to every point.

Approaches

Kruskal Sort All Edges

Solution Details

Reveal Kruskal Sort All Edges: intuition, complexity, and code

Intuition

Every pair of points is a candidate link, so the cheapest network simply takes the cheapest links that avoid cycles. Sorting all pairwise distances and uniting endpoints with a disjoint set builds that network greedily, but materialising every pair costs a heavy edge list, which the optimal approach never stores.

Step-by-Step Logic

Label Example 1 as 0:(0,0), 1:(2,2), 2:(3,10), 3:(5,2), 4:(7,0) and compute all ten pairwise distances.
Sort the links: (1,3) = 3, (0,1) = 4, (3,4) = 4, then (0,3) = 7, (0,4) = 7, (1,4) = 7, (1,2) = 9, and the rest.
Take (1,3) for 3, (0,1) for 4, and (3,4) for 4, uniting {0, 1, 3, 4} at total 11.
Skip (0,3), (0,4), and (1,4): their endpoints already share a group, so each would close a cycle.
Take (1,2) for 9, reaching n - 1 = 4 links at total 20, so return 20.

Why It Works

Accepted edges always form a forest because union rejects endpoints already connected. When a sorted edge joins two components, no lighter unprocessed edge can cross the cut separating either component from the others: a lighter crossing edge would already have merged components. This edge is safe by an exchange argument: in an optimal tree lacking it, add it to create a cycle and remove a crossing edge of at least its weight. The new tree is no more expensive and contains the accepted forest. Repeating this preserves compatibility with an optimal tree until n - 1 accepted edges connect every point. Equal weights need no special tie rule.

Dry Run

Kruskal Sort All Edges: variable states at each step
Link	Distance	Action	Components after	used	Total
initial	-	each point owns a component	{0}, {1}, {2}, {3}, {4}	0	0
(1,3)	3	different roots; take	{0}, {1,3}, {2}, {4}	1	3
(0,1)	4	different roots; take	{0,1,3}, {2}, {4}	2	7
(3,4)	4	different roots; take	{0,1,3,4}, {2}	3	11
(0,3)	7	same root; skip cycle	{0,1,3,4}, {2}	3	11
(0,4)	7	same root; skip cycle	{0,1,3,4}, {2}	3	11
(1,4)	7	same root; skip cycle	{0,1,3,4}, {2}	3	11
(1,2)	9	different roots; take	{0,1,2,3,4}	4	20
answer	-	used = n - 1; stop	one component	4	return 20

Complexity Analysis

Time Complexity

O(n^2 \log n)

Space Complexity

O(n^2)

The complete graph has E = n(n - 1)/2 edges. Building them costs O(n^2); sorting costs O(E log E) = O(n^2 log n), and path-compressed union by rank adds O(E alpha(n)). Edge objects and possible sorting workspace require O(n^2) peak space; parent/rank arrays use O(n), and Java find recursion is at most O(log n) with union by rank. Inputs are not mutated. Each distance is at most 4000000. A chain sorted by x has total horizontal movement at most 2000000 and at most n - 1 vertical movements of 2000000 each, so the minimum total is at most 2000000000 and fits Java int.

Code

Solution.java

1import java.util.List;2import java.util.ArrayList;3
4class Solution {5    public int minCostConnectPoints(int[][] points) {6        int n = points.length;7        List<int[]> edges = new ArrayList<>();8        for (int i = 0; i < n; i++) {9            for (int j = i + 1; j < n; j++) {10                int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);11                edges.add(new int[]{dist, i, j});12            }13        }14        edges.sort((a, b) -> Integer.compare(a[0], b[0]));15        int[] parent = new int[n];16        int[] rank = new int[n];17        for (int i = 0; i < n; i++) {18            parent[i] = i;19        }20        int res = 0;21        int used = 0;22        for (int[] e : edges) {23            if (union(parent, rank, e[1], e[2])) {24                res += e[0];25                used++;26                if (used == n - 1) {27                    break;28                }29            }30        }31        return res;32    }33
34    private int find(int[] parent, int x) {35        if (parent[x] != x) {36            // Compress the path without changing which component owns x.37            parent[x] = find(parent, parent[x]);38        }39        return parent[x];40    }41
42    private boolean union(int[] parent, int[] rank, int a, int b) {43        int ra = find(parent, a);44        int rb = find(parent, b);45        // A same-root edge would close a cycle in the accepted forest.46        if (ra == rb) {47            return false;48        }49        // Only equal ranks increase the merged tree height bound.50        if (rank[ra] < rank[rb]) {51            parent[ra] = rb;52        } else if (rank[ra] > rank[rb]) {53            parent[rb] = ra;54        } else {55            parent[ra] = rb;56            rank[rb]++;57        }58        return true;59    }60}

Hints

Hint 1

Joining all points as cheaply as possible is a minimum spanning tree over the complete graph of Manhattan links.

Hint 2

Kruskal takes the cheapest links first and skips ones joining already-connected points, which a disjoint set detects.

Hint 3

Because every pair of points links, growing one tree with a plain closest-distance array beats storing or sorting every pair.

Edge Cases

A single point, which needs zero links and returns 0.
Two points, where the answer is just their one Manhattan distance.
Points sharing x or y lines, which the absolute-value formula still prices correctly.
Equal distances allow several minimum trees, as in the square example, but the total stays the same.
Negative and extreme coordinates require absolute differences; distinct coordinates ensure every actual edge costs more than zero.

Common Mistakes and Interview Tips

Running unweighted search like plain BFS, which ignores link costs and returns the wrong total.
Forgetting the visited check when attaching the next point, which re-attaches tree points and corrupts the total.
Using Euclidean distance instead of the Manhattan absolute-difference sum required here.
Updating Prim distances with best + dist computes source paths instead of attachment costs and answers a different problem.
Taking every cheapest edge without a component check can create cycles before all vertices are connected.
Interview tip: justify the lightest-crossing-edge choice with a cut exchange argument, and explain why a dense graph favors array Prim over storing all pair edges.

Key Takeaway

On a dense complete graph, growing one tree with a linear closest-distance scan beats sorting every pair.