Free lesson · DSA Mastery - Interview Prep, End to End

Min Cost to Connect All Points

Hard11 min readdsagraphs

Min Cost to Connect All Points

Min Cost to Connect All Points opens the Minimum Spanning Tree (MST) sub-group: given points on a plane, connect them all with minimum total edge cost (the cost between two points is their Manhattan distance), forming a minimum spanning tree. It introduces the two classic MST algorithms - Prim's (grow the tree from a start node, repeatedly adding the cheapest edge to a new node, using a priority queue) and Kruskal's (sort all edges by weight, add each if it doesn't form a cycle, using Union Find for the cycle check). This is the natural continuation of the Union Find sub-group, since Kruskal's algorithm is Union Find applied to spanning-tree construction - the cycle-detection skill from Redundant Connection and Graph Valid Tree now used to build the cheapest connecting tree. We present Prim's (canonical) and Kruskal's (alternative).

The insight: a spanning tree connects all n points with exactly n - 1 edges and no cycles; a minimum spanning tree minimizes the total edge weight. With points on a plane, the graph is complete (every pair is a candidate edge, weighted by Manhattan distance). Prim's grows one tree outward, always absorbing the nearest not-yet-connected point. Kruskal's considers edges globally cheapest-first, adding any that doesn't close a cycle (checked with Union Find). Both produce an MST; the choice often depends on graph density - Prim's suits dense graphs (like this complete one), Kruskal's suits sparse edge lists.

The Problem

You are given an array points representing integer coordinates of some points on a 2D plane, where points[i] = [x_i, y_i].

The cost of connecting two points [x_i, y_i] and [x_j, y_j] is the Manhattan distance between them: |x_i - x_j| + |y_i - y_j|.

Return the minimum cost to make all points connected. All points are connected if there is exactly one simple path between any two points.

Example 1:

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

Explanation: Connecting the points with a minimum spanning tree gives total cost 20.

Example 2:

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

Explanation: The MST over the three points costs 18.

Constraints:

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	Prim's algorithm (grow tree, min-heap)	O(n² log n) or O(n²)	O(n)	Canonical
2	Kruskal's algorithm (sort edges, Union Find)	O(n² log n)	O(n²)	Alternative

Prim's grows the MST from an arbitrary start point: maintain the minimum distance from the tree to each unconnected point, repeatedly add the nearest one (via a min-heap or an O(n) scan), and update neighbors' distances. Kruskal's generates all O(n²) candidate edges, sorts them by Manhattan distance, and adds each edge that connects two different components (Union Find cycle check) until n - 1 edges are chosen. Both yield the MST cost. For this complete graph (dense), Prim's with an O(n²) scan is natural; Kruskal's pays for sorting n² edges.

Approach 1: Prim's Algorithm - Canonical

The Idea

Start with one point in the tree. Maintain minDist[v] = the cheapest edge connecting point v to the current tree (initialized to the distance from the start). Repeatedly pick the unconnected point with the smallest minDist, add it to the tree (accumulating that edge's cost), and update minDist for all remaining unconnected points (each might now be closer to the tree via the newly-added point). After adding all n points, the accumulated cost is the MST total. A min-heap or a simple O(n) scan finds the nearest point each round.

Logic Flowchart

graph TD
    A["minDist[all] = INF; minDist[0] = 0; inTree[all] = false; total = 0"] --> B{"all points in tree?"}
    B -->|Yes| C["return total"]
    B -->|No| D["pick unconnected point u with smallest minDist"]
    D --> E["add u to tree; total += minDist[u]"]
    E --> F["for each unconnected v: minDist[v] = min(minDist[v], dist(u, v))"]
    F --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows Prim's algorithm. Starting from one point, it repeatedly adds the nearest point not yet in the tree, accumulating that edge's cost and updating each remaining point's distance to the growing tree.

Code

public static int minCostConnectPoints(int[][] points) {
    int n = points.length;
    int[] minDist = new int[n];
    boolean[] inTree = new boolean[n];
    Arrays.fill(minDist, Integer.MAX_VALUE);
    minDist[0] = 0;                                    // start the tree at point 0
    int total = 0;

    for (int iter = 0; iter < n; iter++) {
        int u = -1;                                    // find nearest unconnected point
        for (int v = 0; v < n; v++)
            if (!inTree[v] && (u == -1 || minDist[v] < minDist[u])) u = v;

        inTree[u] = true;
        total += minDist[u];                           // add its connecting edge

        for (int v = 0; v < n; v++)                    // relax neighbors' distances
            if (!inTree[v]) {
                int d = Math.abs(points[u][0] - points[v][0])
                      + Math.abs(points[u][1] - points[v][1]);   // Manhattan distance
                if (d < minDist[v]) minDist[v] = d;
            }
    }
    return total;
}

// Usage:
// minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]]) -> 20
// minCostConnectPoints([[3,12],[-2,5],[-4,1]]) -> 18

This Java code computes the minimum spanning tree cost with Prim's algorithm: it repeatedly adds the nearest unconnected point to the tree, accumulating that edge's Manhattan distance and updating remaining points' distances.

Step-by-Step Walkthrough

A frame-by-frame trace on Example 2, [[3,12],[-2,5],[-4,1]]:

graph LR
    F0["distances: d(0,1)=|3-(-2)|+|12-5|=12, d(0,2)=|3-(-4)|+|12-1|=18, d(1,2)=|-2-(-4)|+|5-1|=6"]
    F1["start at 0. minDist=[0,12,18]. pick 0, total=0. relax: minDist=[0,12,18]"]
    F2["pick nearest unconnected=1 (12). total=12. relax via 1: minDist[2]=min(18, d(1,2)=6)=6"]
    F3["pick 2 (6). total=12+6=18. all in tree → return 18"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough builds an MST: starting at point zero, the tree absorbs point one at cost twelve, then point two at cost six via the cheaper edge, totaling eighteen.

Result: 18.

Complexity

Time: O(n²) with the array scan (ideal for this dense complete graph); O(n² log n) with a heap. Space: O(n) for minDist and inTree.

Approach 2: Kruskal's Algorithm - Alternative

The Idea

Generate all O(n²) candidate edges (every pair, weighted by Manhattan distance). Sort them ascending by weight. Process edges cheapest-first: for each, if its two points are in different components (Union Find check), add it to the MST (accumulate cost, union them); skip it otherwise (it would form a cycle). Stop once n - 1 edges are added - the MST is complete.

Code

public static int minCostConnectPointsKruskal(int[][] points) {
    int n = points.length;
    List<int[]> edges = new ArrayList<>();             // {weight, i, j}
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++) {
            int d = Math.abs(points[i][0] - points[j][0])
                  + Math.abs(points[i][1] - points[j][1]);
            edges.add(new int[]{d, i, j});
        }
    edges.sort((a, b) -> a[0] - b[0]);                 // cheapest edges first

    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
    int total = 0, used = 0;
    for (int[] e : edges) {
        int ri = find(parent, e[1]), rj = find(parent, e[2]);
        if (ri != rj) {                                // no cycle → add to MST
            parent[ri] = rj;
            total += e[0];
            if (++used == n - 1) break;                // MST complete
        }
    }
    return total;
}

private static int find(int[] parent, int x) {
    while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; }
    return x;
}

// Usage: minCostConnectPointsKruskal([[3,12],[-2,5],[-4,1]]) -> 18

This Java code computes the MST cost with Kruskal's algorithm: it sorts all candidate edges by Manhattan distance and adds each edge that connects two different components, using Union Find to skip cycle-forming edges.

Complexity

Time: O(n² log n) - sorting n² edges dominates. Space: O(n²) for the edge list.

Complexity Comparison

Approach	Time	Space	Key Idea
Prim's (array scan)	O(n²)	O(n)	Grow tree; add nearest unconnected point
Kruskal's (sort + Union Find)	O(n² log n)	O(n²)	Sort edges; add cheapest non-cycle edges

Both build the MST. Prim's grows a single tree outward, adding the nearest unconnected point each round - with an O(n) scan it's O(n²), ideal for this dense complete graph (no need to materialize n² edges). Kruskal's sorts all edges and adds cheapest-first using Union Find to skip cycles - natural for sparse graphs given as edge lists, but here it pays O(n² log n) to sort. The choice hinges on density; both are foundational MST algorithms.

Variations & Follow-ups

What is a minimum spanning tree, and why exactly n-1 edges?

A spanning tree of a connected graph on n nodes is a subset of edges that (1) connects all n nodes and (2) contains no cycles - i.e., it's a tree spanning every vertex. As established in Graph Valid Tree, a tree on n nodes has exactly n - 1 edges: fewer can't connect all nodes (disconnected), more must create a cycle. A minimum spanning tree (MST) is a spanning tree whose total edge weight is the smallest among all possible spanning trees. The MST problem - connect everything as cheaply as possible - models countless real scenarios: laying network cable, road/pipe/power-grid construction, clustering. Here, "connect all points" with minimum total Manhattan distance is exactly the MST of the complete graph where every pair of points is an edge weighted by their distance. The n - 1 edge count is structural: any valid answer is a spanning tree, so it uses exactly n - 1 edges. Both Prim's and Kruskal's exploit this - Prim's adds points until all n are in the tree (n - 1 edges added), and Kruskal's stops once n - 1 non-cycle edges are chosen. Understanding "MST = cheapest tree connecting everything = exactly n - 1 edges, acyclic, connected" frames the whole sub-group; it directly extends the tree characterization from Graph Valid Tree, now with a minimization objective.

How does Prim's algorithm work, and why is the greedy choice correct?

Prim's grows the MST as a single expanding tree. Start with any one node in the tree. At each step, look at all edges crossing from the tree to the outside, and add the cheapest such edge (and the new node it reaches). Repeat until all nodes are in the tree. The implementation tracks minDist[v] - the cheapest single edge connecting unconnected node v to the current tree - picks the unconnected node with the smallest minDist (the cheapest way to grow), adds it, then relaxes: for each still-unconnected node, checks whether the newly-added node offers a cheaper connection and updates minDist accordingly. Why is this greedy choice correct? The cut property of MSTs: for any partition of the nodes into two sets (here, "in the tree" vs. "outside"), the minimum-weight edge crossing the cut is safe to include in some MST. Prim's always adds exactly that minimum crossing edge, so every edge it adds is MST-safe, and after n - 1 additions it has a complete MST. The greedy "always grow by the cheapest boundary edge" never regrets - the cut property guarantees it. This is why Prim's is correct: each local cheapest-expansion is provably part of an optimal global tree. The relaxation step (updating minDist after each addition) keeps the "cheapest edge to the tree" current as the tree grows, mirroring the relaxation in Dijkstra (the algorithms are structurally similar - Prim's minimizes the edge to the tree, Dijkstra minimizes the path from the source).

How does Kruskal's algorithm work, and why is it Union Find applied to MSTs?

Kruskal's builds the MST globally, edge by edge, from cheapest to most expensive. Sort all edges ascending by weight. Process each edge in turn: if its two endpoints are in different components, add it to the MST (it safely connects two pieces); if they're in the same component, skip it (adding it would form a cycle, and a tree has no cycles). Stop once n - 1 edges are added. The cycle check - "are these two endpoints already connected?" - is exactly the Union Find operation from Redundant Connection and Graph Valid Tree: find(a) == find(b) tests whether the edge would close a cycle, and union(a, b) records the merge when the edge is added. So Kruskal's is Union Find applied to spanning-tree construction: it greedily takes cheapest edges, using Union Find to maintain the growing forest and reject cycle-forming edges. This is why the MST sub-group follows Union Find directly - you already have the core machinery. Why is Kruskal's greedy choice correct? The cycle property (dual to the cut property): the cheapest edge that doesn't form a cycle is always MST-safe. Processing edges cheapest-first and skipping cycle-formers means every added edge is the cheapest available safe edge, yielding an optimal tree. Kruskal's shines on sparse graphs (few edges to sort); for this dense complete graph (n² edges), sorting is the bottleneck, making Prim's array-scan version faster. But conceptually, Kruskal's beautifully reuses the Union Find cycle detection you've already mastered.

When do you choose Prim's vs. Kruskal's, and how do they relate to other algorithms?

Both produce a correct MST in similar asymptotic time, so the choice hinges on graph density and representation. Prim's is preferable for dense graphs (many edges, like this complete graph) - with an adjacency-matrix/array-scan implementation it's O(V²), avoiding the cost of enumerating and sorting all edges; with a binary heap it's O(E log V). It's also natural when the graph is given implicitly (compute edge weights on demand, as with point distances). Kruskal's is preferable for sparse graphs given as an edge list - sorting E edges (O(E log E)) plus near-constant Union Find operations is efficient when E is small relative to V². For this problem's complete graph (E = O(n²)), Prim's O(n²) scan beats Kruskal's O(n² log n) sort, which is why Prim's is canonical here. The algorithms also connect to broader ideas: Prim's is structurally Dijkstra-like (a priority-queue-driven greedy frontier expansion, minimizing the edge-to-tree rather than path-from-source), tying back to the priority-queue best-first search seen in Path With Maximum Minimum Value and ahead in the Shortest Path sub-group. Kruskal's is Union Find's flagship application. Knowing both - and when each is faster (dense → Prim's, sparse → Kruskal's) - is the practical MST skill. Both rest on the same greedy MST theory (cut and cycle properties), just applied tree-growing-outward (Prim's) versus globally-cheapest-edge (Kruskal's).

What about edge cases?

Single point (n == 1): No edges needed; cost 0.
Two points: One edge; cost is their Manhattan distance.
Collinear or clustered points: The MST still uses n - 1 cheapest connecting edges.
All equal pairwise distances: Any spanning tree is minimum; cost is (n-1) × distance.
Large coordinates: Manhattan distances can be large; use sufficient integer width for the total.

Common Interview Pitfalls

Materializing all n² edges for Prim's. Prim's array-scan computes distances on the fly in O(n²) - no edge list needed; only Kruskal's needs the sorted edges.
Forgetting to relax after each Prim's addition. Update minDist for unconnected nodes via the newly-added node, or you miss cheaper connections.
Kruskal's: not stopping at n-1 edges. You can break early once the tree is complete.
Decrementing/adding on cycle edges in Kruskal's. Add an edge only when find(a) != find(b); skip cycle-formers.

Why This Topic Matters

Min Cost to Connect All Points introduces the minimum spanning tree and its two classic algorithms: Prim's (grow one tree, always adding the cheapest edge to a new node - O(n²) for dense graphs) and Kruskal's (sort edges, add cheapest non-cycle edges via Union Find - ideal for sparse graphs). Both rest on the greedy cut/cycle properties. Kruskal's is the Union Find cycle-detection skill from earlier applied to tree-building, making MST the natural successor to the Union Find sub-group; Prim's previews Dijkstra's priority-queue expansion.

The next topic, Connecting Cities With Minimum Cost, is a direct MST application on an explicit weighted edge list: given n cities and a list of weighted connections, find the minimum cost to connect all cities (return -1 if impossible). Unlike the complete-graph point problem, here the edges are given explicitly and sparsely, making it the textbook setting for Kruskal's algorithm - sort the given edges by cost, add each non-cycle edge via Union Find, and detect impossibility (the graph can't be fully connected) when fewer than n - 1 edges are usable. It cements Kruskal's on a sparse edge list and adds the connectivity-feasibility check (return -1 if the cities can't all be connected).

Back to DSA Mastery - Interview Prep, End to End