Min Cost to Connect All Points

NeetCode: Min Cost to Connect All Points · LeetCode: 1584. Min Cost to Connect All Points · Difficulty: Medium

You are given points on a 2D plane. The cost of connecting two points is their Manhattan distance |x1 - x2| + |y1 - y2|. Return the minimum total cost to connect all points so that there is exactly one simple path between any two of them.

Example

Text

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

The answer is the weight of the minimum spanning tree (MST) of the complete graph on the points. Two classic algorithms compute it: Kruskal (sort edges, add the cheapest that joins two components) and Prim (grow one tree by repeatedly adding the cheapest edge leaving it). On a complete graph with n vertices, the dense form of Prim runs in O(n^2) and Kruskal in O(n^2 log n).

Brute force: Kruskal with every edge sorted

Build all n * (n - 1) / 2 edges, sort them by cost, and take an edge whenever its endpoints are in different components (tracked with union-find). Stop after n - 1 edges. The greedy choice is valid by the cut property: the cheapest edge crossing any cut belongs to some MST.

Each edge is an int[]{cost, a, b}. The distance is computed in long so differences of large coordinates cannot overflow int, and the sort compares costs with Long.compare.

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
    private int find(int[] parent, int x) {
        int root = x;
        while (parent[root] != root) root = parent[root];
        while (parent[x] != root) { // path compression
            int next = parent[x];
            parent[x] = root;
            x = next;
        }
        return root;
    }

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        List<long[]> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long d = Math.abs((long) points[i][0] - points[j][0])
                        + Math.abs((long) points[i][1] - points[j][1]);
                edges.add(new long[] {d, i, j});
            }
        }
        edges.sort((a, b) -> Long.compare(a[0], b[0]));

        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        long total = 0;
        int used = 0;
        for (long[] e : edges) {
            int ra = find(parent, (int) e[1]);
            int rb = find(parent, (int) e[2]);
            if (ra != rb) {
                parent[ra] = rb;
                total += e[0];
                used++;
                if (used + 1 == n) break;
            }
        }
        return (int) total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minCostConnectPoints(new int[][] {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}}));
        System.out.println(s.minCostConnectPoints(new int[][] {{3, 12}, {-2, 5}, {-4, 1}}));
        System.out.println(s.minCostConnectPoints(new int[][] {{1, 1}}));
    }
}

Output

20
18
0

Sorting O(n^2) edges dominates. Time: O(n^2 log n). Space: O(n^2) for the edge list.

Optimal: Prim's algorithm with a distance array

Because every pair of points is an edge, a heap does not help; the dense version of Prim needs no edge list. Keep dist[i], the cheapest known cost to attach point i to the tree. Repeatedly pick the point not yet in the tree with the smallest dist, add it, and relax the distances of the remaining points using the newly added point. Each of the n rounds scans O(n) points.

Java

import java.util.Arrays;

class Solution {
    private long manhattan(int[][] points, int a, int b) {
        return Math.abs((long) points[a][0] - points[b][0])
                + Math.abs((long) points[a][1] - points[b][1]);
    }

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        if (n == 0) return 0;
        boolean[] inTree = new boolean[n];
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[0] = 0;
        long total = 0;
        for (int round = 0; round < n; round++) {
            // Pick the closest point that is not in the tree yet.
            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]) dist[v] = Math.min(dist[v], manhattan(points, u, v));
            }
        }
        return (int) total;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.minCostConnectPoints(new int[][] {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}}));
        System.out.println(s.minCostConnectPoints(new int[][] {{3, 12}, {-2, 5}, {-4, 1}}));
        System.out.println(s.minCostConnectPoints(new int[][] {{1, 1}}));
    }
}

Output

20
18
0

Time: O(n^2). Space: O(n). Compared with Kruskal, Prim saves the log n factor and avoids storing the quadratic edge list.