Problem 27.1 · Minimum Spanning TreesMedium

Min Cost to Connect All Points

What it teaches: MST on a complete graph: array-based Prim without building the edges.

Practise it on judges as “Min Cost to Connect All Points”.

The problem

Connecting two points costs their Manhattan distance |x1 − x2| + |y1 − y2|. Return the minimum cost to connect all points.

Example 1

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

Constraints

1 ≤ n ≤ 1000

Pattern clues in the wording

→ Connect everything, minimum total
→ Every pair is a possible edge

These clues point to Minimum Spanning Tree: Connect all nodes with the cheapest total edges: sort edges and add each one that doesn't form a cycle (Kruskal).

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int minCostConnectPoints(int[][] points) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

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

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Prim with arrays · O(n²)2. Kruskal over all pairs · O(n² log n)

Prim with arrays

Time O(n²) Space O(n)

best[v] = cheapest connection to the tree. Repeat n times: pick the cheapest outside point, add its cost, update best for the rest.

Approach 1

import java.util.Arrays;

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

Verdict: Optimal for complete graphs.

Kruskal over all pairs

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

Generate all n(n − 1)/2 edges, sort, and union until n − 1 are taken.

Approach 2

import java.util.*;

class Solution {
    private int[] parent;

    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++)
                edges.add(new int[]{Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]), i, j});
        edges.sort(Comparator.comparingInt(e -> e[0]));
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int total = 0, used = 0;
        for (int[] e : edges) {
            if (used == n - 1) break;
            int a = find(e[1]), b = find(e[2]);
            if (a == b) continue;
            parent[a] = b;
            total += e[0];
            used++;
        }
        return total;
    }

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

Verdict: Works, but heavier on memory.

Before you submit

Edge cases and common mistakes

Test these inputs

One point (0)
Duplicate points (distance 0)

Mistakes people make

Using Euclidean distance.

Interview

Follow-up questions

Can you avoid O(n²) for huge n?