Min Cost to Connect All Points

mediumAdvanced Graphs (Dijkstra / MST)177 stepsJava · Python · C++

Connect all points with the least total Manhattan distance: a minimum spanning tree. Prim's algorithm grows the tree one point at a time, always adding the cheapest edge from the tree to a point outside it. On a dense graph, an O(n²) array version beats using a heap.

▶ Watch the animated trace

Traced input: points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]] → 20. Original problem: neetcode.io/problems/min-cost-to-connect-points

Complexity

BestO(n²)

AverageO(n²)

WorstO(n²)

SpaceO(n)

Every pair of points is a potential edge.

Key idea

dist[i] = cheapest edge connecting point i to the tree so far.
Each round, add the outside point with the smallest dist.
Then update dist for the remaining points using the new point.
Kruskal with union-find also works, but needs all n² edges sorted.

Common mistakes

Building all n² edges into a heap uses a lot of memory.
Using Euclidean instead of Manhattan distance.

Solution

Java

int minCostConnectPoints(int[][] points) {
    int n = points.length, total = 0;
    int[] dist = new int[n];
    boolean[] inTree = new boolean[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[0] = 0;
    for (int round = 0; round < n; round++) {
        int u = -1;
        for (int i = 0; i < n; i++)
            if (!inTree[i] && (u == -1 || dist[i] < dist[u])) u = i;
        inTree[u] = true;
        total += dist[u];
        for (int v = 0; v < n; v++) {
            int d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
            if (!inTree[v] && d < dist[v]) {
                dist[v] = d;
            }
        }
    }
    return total;
}

Python

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

C++

int minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size(), total = 0;
    vector<int> dist(n, INT_MAX);
    vector<bool> inTree(n);
    dist[0] = 0;
    for (int round = 0; round < n; round++) {
        int u = -1;
        for (int i = 0; i < n; i++)
            if (!inTree[i] && (u == -1 || dist[i] < dist[u])) u = i;
        inTree[u] = true;
        total += dist[u];
        for (int v = 0; v < n; v++) {
            int d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1]);
            if (!inTree[v] && d < dist[v]) {
                dist[v] = d;
            }
        }
    }
    return total;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single point Nothing to connect.	`points = [[0, 0]]`	`0`
Two points \|1\| + \|1\| = 2.	`points = [[0, 0], [1, 1]]`	`2`
Negative coordinates Both edges to the middle point cost 2.	`points = [[-1, -1], [1, 1], [0, 0]]`	`4`