Min Cost to Connect All Points

MediumGraphs · Minimum Spanning Tree🧩 MST & Euler Paths LeetCode #1584 ↗Updated Oct 30, 2026

Problem

You get n distinct points on a 2D plane. Linking two points costs their Manhattan distance |x1-x2| + |y1-y2|. Return the minimum total cost so that every point is connected to every other (directly or through other points).

Input[[0,0],[2,2],[3,10],[5,2],[7,0]]Output20

Input[[3,12],[-2,5],[-4,1]]Output18

1 ≤ n ≤ 1000 · -10⁶ ≤ x_i, y_i ≤ 10⁶ · all points distinct

Try it yourself

Java

class Solution {
    public int minCostConnectPoints(int[][] points) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

It is an MST on a complete graph (E ≈ n²/2): array-based Prim in O(n²) beats sorting or heaping the edges.

PatternMST & Euler Paths

Instinct "Connect every point for the least total cost" means a minimum spanning tree; "use every edge or ticket exactly once" means an Euler path.

Memory hack MST - grab the cheapest bridge that joins two separate islands. Euler - wander until stuck, write the stop down on the way back, then reverse.

Open the MST & Euler Paths guide →

Approaches

Brute ForceKruskal on All Pairs (Sort + Union-Find)

Time O(n² log n)Space O(n²)

Materialise all n(n-1)/2 edges, sort by cost, and greedily take each edge that joins two different components (checked with Union-Find). By the cut property the cheapest edge across any cut is always safe; stop at n-1 edges.

Java

public int minCostConnectPoints(int[][] points) {
    int n = points.length, cost = 0, used = 0;
    List<int[]> edges = new ArrayList<>();
    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((x, y) -> x[0] - y[0]);
    int[] parent = IntStream.range(0, n).toArray(); // each point is its own set
    for (int[] e : edges) {
        int ra = find(parent, e[1]), rb = find(parent, e[2]);
        if (ra == rb) continue; // would close a cycle
        parent[ra] = rb;
        cost += e[0];
        if (++used == n - 1) break;
    }
    return cost;
}
private int find(int[] parent, int x) {
    return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}

Classic and correct, but stores and sorts ~500k edges for n = 1000.

BetterPrim with a Min-Heap

Time O(n² log n)Space O(n²)

Grow one tree from point 0. Pop the cheapest {point, cost}; skip it if already in the tree, else add it and push every outside point whose distance to it improves minDist. Edges are generated on the fly, never stored up front.

Java

public int minCostConnectPoints(int[][] points) {
    int n = points.length, cost = 0;
    boolean[] inTree = new boolean[n];
    int[] minDist = new int[n];
    Arrays.fill(minDist, Integer.MAX_VALUE);
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{0, 0}); // {point, cost to attach}
    while (!pq.isEmpty()) {
        int[] cur = pq.poll(); int u = cur[0];
        if (inTree[u]) continue; // stale entry
        inTree[u] = true;
        cost += cur[1];
        for (int v = 0; v < n; v++) {
            if (inTree[v]) continue;
            int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
            if (d < minDist[v]) { minDist[v] = d; pq.offer(new int[]{v, d}); }
        }
    }
    return cost;
}

No edge list, but the heap can still hold O(n²) stale entries.

OptimalPrim with a Plain Array (Dense Graph)

Time O(n²)Space O(n)

Same greedy, but choose the next point by a linear scan of minDist: n rounds × O(n) pick + O(n) relax = O(n²), exactly the number of edges we must inspect anyway.

Java

public int minCostConnectPoints(int[][] points) {
    int n = points.length, cost = 0;
    int[] minDist = new int[n];
    boolean[] inTree = new boolean[n];
    Arrays.fill(minDist, Integer.MAX_VALUE);
    minDist[0] = 0;
    for (int round = 0; round < n; round++) {
        int u = -1;
        for (int v = 0; v < n; v++) // cheapest point outside the tree
            if (!inTree[v] && (u == -1 || minDist[v] < minDist[u])) u = v;
        inTree[u] = true;
        cost += minDist[u];
        for (int v = 0; v < n; v++) {
            if (inTree[v]) continue;
            int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
            minDist[v] = Math.min(minDist[v], d);
        }
    }
    return cost;
}

Optimal for a complete graph: every edge is touched once, no log factor.

At a glance

Level	Approach	Time	Space
Brute Force	Kruskal on All Pairs (Sort + Union-Find)	`O(n² log n)`	`O(n²)`
Better	Prim with a Min-Heap	`O(n² log n)`	`O(n²)`
Optimal	Prim with a Plain Array (Dense Graph)	`O(n²)`	`O(n)`

Common pitfalls

Forgetting if (inTree[u]) continue in heap Prim — double-counts cost.
Using Euclidean instead of Manhattan distance.
Running Dijkstra (path sums) instead of Prim (single edge cost).

Interview tips

Name it immediately: “connect everything at min total cost” = MST.
Point out E = O(n²), which is why array Prim wins here.
Know both Kruskal and Prim; justify them with the cut property.

Pattern

Minimum Spanning Tree → link all nodes with the least total edge weight, no cycles needed.

My notes saved in this browser