150NeetCode 150

94.Min Cost to Connect All Points

MediumGraphs · 15/19
LeetCode #1584Video

Problem

You are given an array points where points[i] = [xi, yi] is a point on a 2D plane. The cost of connecting two points is their Manhattan distance: |xi - xj| + |yi - yj|.

Return the minimum total cost to connect all points so that there is exactly one simple path between any two points (i.e. the connections form a spanning tree).

Examples

Input:  points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: Connect (0,0)-(2,2)=4, (2,2)-(5,2)=3, (5,2)-(7,0)=4, (2,2)-(3,10)=9. Total = 20.
Input:  points = [[3,12],[-2,5],[-4,1]]
Output: 18
Explanation: (3,12)-(-2,5)=12 and (-2,5)-(-4,1)=6.
Input:  points = [[0,0]]
Output: 0

Constraints

  • 1 <= points.length <= 1000
  • -10^6 <= xi, yi <= 10^6
  • All pairs (xi, yi) are distinct.

💡 Key Insight

This is a Minimum Spanning Tree on a complete graph: every pair of points is a potential edge, so E = n(n-1)/2 ≈ 500,000. Kruskal and heap-based Prim both work, but they pay log factors on half a million edges. Because the graph is dense, the array-based Prim's algorithm — which keeps a minDist[] to the growing tree and scans for the closest outside point — runs in O(n²) with O(n) memory and never materialises the edge list.

Kruskal's Algorithm

TimeO(n² log n)SpaceO(n²)

Intuition

Generate every pair (i, j) with its Manhattan distance, sort the edges by cost, and add them cheapest first. Use Union-Find to skip any edge whose endpoints are already connected (it would form a cycle). Stop after n - 1 edges.

Algorithm

  1. Build all n(n-1)/2 edges [cost, i, j] and sort by cost.
  2. Initialise Union-Find over n points.
  3. For each edge in order: if union(i, j) succeeds, add cost and increment used; stop when used == n - 1.
  4. Return the total.

Visualization

points: A(0,0) B(2,2) C(3,10) D(5,2) E(7,0)

sorted edges: B-D 3, A-B 4, D-E 4, A-D 7, B-E 7, ... B-C 9, C-D 10, ...
take B-D 3   {B,D}
take A-B 4   {A,B,D}
take D-E 4   {A,B,D,E}
skip A-D 7   (cycle)   skip B-E 7 (cycle) ...
take B-C 9   {A,B,C,D,E}  -> 4 edges, total = 20

Code

java
import java.util.Arrays;

class Solution {
    private int[] parent;

    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        int[][] edges = new int[n * (n - 1) / 2][];
        int k = 0;
        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[k++] = new int[] {cost, i, j};
            }
        }
        Arrays.sort(edges, (a, b) -> Integer.compare(a[0], b[0]));

        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        int total = 0;
        int used = 0;
        for (int[] e : edges) {
            if (used == n - 1) {
                break; // spanning tree complete
            }
            int rootA = find(e[1]);
            int rootB = find(e[2]);
            if (rootA != rootB) {
                parent[rootA] = rootB;
                total += e[0];
                used++;
            }
        }
        return total;
    }

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

Complexity

  • Time: O(n² log n) — sorting n²/2 edges dominates.
  • Space: O(n²) — the full edge list.

Complexity Comparison

Approach Time Space
Kruskal's Algorithm O(n² log n) O(n²)
Prim's with Min-Heap O(n² log n) O(n²)
Prim's with Array O(n²) O(n)

Common Pitfalls

  • Using Euclidean distance instead of Manhattan distance.
  • Forgetting the single-point case — the answer is 0, and Kruskal must not allocate a negative-size array (n(n-1)/2 = 0 is fine).
  • In heap-based Prim, not skipping stale entries for points already in the tree, which double-counts costs.
  • Assuming a sparse-graph algorithm is fastest here — with n² edges, the O(n²) array version wins.