Problem statement

You are given 2D points. The cost of connecting two points is their Manhattan distance |x1-x2| + |y1-y2|.

Return the minimum total cost to make all points connected (exactly one simple path between every pair).

Example 1

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

Example 2

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

Constraints

• 1 <= points.length <= 10
• -100 <= coordinates <= 100

Hints for Min Cost to Connect All Points

1. Hint 1

   This is a Minimum Spanning Tree on the complete graph of points.

2. Hint 2

   Prim's algorithm with an array of best-known distances is O(n²) — plenty here.

How to solve Min Cost to Connect All Points

Connecting all points with exactly one path between every pair means building a spanning tree, and "minimum total cost" makes it a Minimum Spanning Tree. Every pair of points is joinable, so the graph is complete — which makes Prim's algorithm with a simple array of best-known distances the natural fit at O(n^2), with no edge list to build.

Approach

1. Keep inTree[v] and minDist[v], the cheapest known edge from the growing tree to v. Start with minDist[0] = 0 and everything else infinite.
2. Repeat n times: pick the point not yet in the tree with the smallest minDist.
3. Add it to the tree and add its minDist to the running total.
4. For every point still outside, recompute its Manhattan distance to the newly added point and keep it if it beats the current minDist.
5. After n rounds every point is connected and the total is the MST cost.

Why it works

Prim's rests on the cut property: for any split of the points into "in the tree" and "not yet", the cheapest edge crossing that split belongs to some MST. Each round picks exactly that edge — minDist holds, for every outside point, the cost of the cheapest edge to the tree, so its minimum is the cheapest crossing edge. Growing the tree one safe edge at a time yields an MST after n - 1 additions; the seed contributes 0.

Complexity

• Time — O(n^2)
• Space — O(n)

Pitfalls

• A single point costs 0 — guard the trivial case so the loop does not add an infinite minDist.
• Update minDist only for points outside the tree; touching those already inside can corrupt the running minimum.
• The metric is Manhattan (|dx| + |dy|), not Euclidean.
• The seed's minDist must be 0, otherwise the total is off by the first edge.

Reference solution

Python

from typing import List

def minCostConnectPoints(points: List[List[int]]) -> int:
    n = len(points)
    if n <= 1:
        return 0
    INF = float("inf")
    in_tree = [False] * n
    min_dist = [INF] * n
    min_dist[0] = 0
    total = 0
    for _ in range(n):
        u = -1
        for v in range(n):
            if not in_tree[v] and (u == -1 or min_dist[v] < min_dist[u]):
                u = v
        in_tree[u] = True
        total += min_dist[u]
        for v in range(n):
            if not in_tree[v]:
                d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
                if d < min_dist[v]:
                    min_dist[v] = d
    return total

Java

public static int minCostConnectPoints(int[][] points) {
    int n = points.length;
    if (n <= 1) return 0;
    final int INF = 1000000000;
    boolean[] inTree = new boolean[n];
    int[] minDist = new int[n];
    Arrays.fill(minDist, INF);
    minDist[0] = 0;
    int total = 0;
    for (int iter = 0; iter < n; iter++) {
        int u = -1;
        for (int v = 0; v < n; v++) {
            if (!inTree[v] && (u == -1 || minDist[v] < minDist[u])) u = v;
        }
        inTree[u] = true;
        total += minDist[u];
        for (int v = 0; v < n; v++) {
            if (!inTree[v]) {
                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;
            }
        }
    }
    return total;
}

C++

int minCostConnectPoints(vector<vector<int>>& points) {
    int n = (int) points.size();
    if (n <= 1) return 0;
    const int INF = 1000000000;
    vector<bool> inTree(n, false);
    vector<int> minDist(n, INF);
    minDist[0] = 0;
    int total = 0;
    for (int iter = 0; iter < n; iter++) {
        int u = -1;
        for (int v = 0; v < n; v++) {
            if (!inTree[v] && (u == -1 || minDist[v] < minDist[u])) u = v;
        }
        inTree[u] = true;
        total += minDist[u];
        for (int v = 0; v < n; v++) {
            if (!inTree[v]) {
                int d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
                if (d < minDist[v]) minDist[v] = d;
            }
        }
    }
    return total;
}

JavaScript

var minCostConnectPoints = function(points) {
    const n = points.length;
    if (n <= 1) return 0;
    const inTree = new Array(n).fill(false);
    const minDist = new Array(n).fill(Infinity);
    minDist[0] = 0;
    let total = 0;
    for (let iter = 0; iter < n; iter++) {
        let u = -1;
        for (let v = 0; v < n; v++) {
            if (!inTree[v] && (u === -1 || minDist[v] < minDist[u])) u = v;
        }
        inTree[u] = true;
        total += minDist[u];
        for (let v = 0; v < n; v++) {
            if (!inTree[v]) {
                const d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
                if (d < minDist[v]) minDist[v] = d;
            }
        }
    }
    return total;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More graph problems

• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium
• Power Grid Maintenance Medium
• Minimum Time to Reach Destination in Directed Graph Medium
• Unit Conversion I Medium
• Digit Operations to Make Two Integers Equal Medium