Min Cost to Connect All Points

Medium Problem 114 of 151 Java and Python

Problem

You are given an array points where points[i] = [xᵢ, yᵢ]. Connecting two points costs their Manhattan distance |xᵢ - xⱼ| + |yᵢ - yⱼ|.

Return the minimum cost to connect all points, so that there is exactly one path between any two points.

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 ≤ 1000
All points are distinct.

Explanation

Connecting everything with exactly one path between any two points is a spanning tree; the cheapest one is a minimum spanning tree (MST).

Kruskal: sort all edges by cost and add each one that joins two different components (Union-Find). Prim: grow one tree, always adding the cheapest edge to a point not yet in it. Here every pair is an edge (a dense graph), so an O(n²) Prim with an array is the fastest.

Approach 1 · Better

Kruskal with Union-Find

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

List every pair as an edge, sort by cost, and add edges that connect two separate components until n - 1 edges are used.

Build all n(n - 1)/2 edges with their costs; sort them.
For each edge, if find(i) != find(j), union them and add the cost.
Stop after n - 1 edges.

Java

import java.util.*;

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int cost = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                edges.add(new int[] { cost, i, j });
            }
        }
        edges.sort((a, b) -> Integer.compare(a[0], b[0]));
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        int total = 0;
        int used = 0;
        for (int[] e : edges) {
            int a = find(parent, e[1]);
            int b = find(parent, e[2]);
            if (a != b) {
                parent[a] = b;
                total += e[0];
                if (++used == n - 1) {
                    break;
                }
            }
        }
        return total;
    }

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

Python

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        edges = sorted(
            (abs(x1 - x2) + abs(y1 - y2), i, j)
            for i, (x1, y1) in enumerate(points)
            for j, (x2, y2) in enumerate(points) if i < j
        )
        parent = list(range(n))

        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        total = used = 0
        for cost, i, j in edges:
            a, b = find(i), find(j)
            if a != b:
                parent[a] = b
                total += cost
                used += 1
                if used == n - 1:
                    break
        return total

Approach 2 · Optimal

Prim with a distance array

Time O(n²)
Space O(n)

Grow the tree from point 0. Keep, for every point outside the tree, its cheapest connection to the tree; repeatedly add the point with the smallest one.

dist[i] = infinity for all, dist[0] = 0.
Repeat n times: pick the unvisited point u with the smallest dist; add dist[u] to the total and mark it.
For every unvisited v, dist[v] = min(dist[v], cost(u, v)).

Java

import java.util.*;

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;
        boolean[] inTree = new boolean[n];
        int total = 0;
        for (int step = 0; step < n; step++) {
            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++) {
                if (!inTree[v]) {
                    int cost = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
                    dist[v] = Math.min(dist[v], cost);
                }
            }
        }
        return total;
    }
}

Python

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        dist = [float("inf")] * n
        dist[0] = 0
        in_tree = [False] * n
        total = 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]
            ux, uy = points[u]
            for v in range(n):
                if not in_tree[v]:
                    dist[v] = min(dist[v], abs(ux - points[v][0]) + abs(uy - points[v][1]))
        return total

Complexity compared

Approach	Time	Space
Better Kruskal with Union-Find	O(n² log n)	O(n²)
Optimal Prim with a distance array	O(n²)	O(n)

Key takeaways

Kruskal suits sparse graphs (few edges); array-based Prim suits dense graphs like "every pair is connected".

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem