351. Min Cost to Connect All Points

We want the minimum spanning tree of the complete graph where edge weight is Manhattan distance. Kruskal's algorithm picks the cheapest edges first and adds the ones that don't create a cycle.

Approach

1. Generate all O(n²) edges with their Manhattan distances.
2. Sort edges by weight.
3. Walk them in order; use Union-Find to skip edges that would form a cycle. Add weight when an edge merges two components.
4. Stop after n - 1 edges.

Complexity

• Time: O(n² · log n) — sorting dominates.
• Space: O(n²) — the edge list.

import java.util.*;

class Solution {
    private int[] parent;

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

    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 dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                edges.add(new int[]{dist, i, j});
            }
        }
        edges.sort((a, b) -> Integer.compare(a[0], b[0]));
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        int cost = 0, used = 0;
        for (int[] edge : edges) {
            int ra = find(edge[1]), rb = find(edge[2]);
            if (ra != rb) {
                parent[ra] = rb;
                cost += edge[0];
                used++;
                if (used == n - 1) break;
            }
        }
        return cost;
    }
}

Prim's algorithm grows a tree one vertex at a time, always reaching out to the cheapest neighbour available. Because every pair of points has an edge in this problem, we don't need a heap of edges — a flat array min_dist[v] tracking the cheapest distance from the current tree to each outsider is enough. With n ≤ 1000 the dense O(n²) form is faster than the heap-based one because it avoids logarithmic overhead.

What's an MST?

A Minimum Spanning Tree of a connected weighted graph is a subset of edges that:

• Touches every vertex (spans the graph),
• Forms no cycles (it's a tree),
• Has the smallest possible total edge weight.

In this problem the graph is the complete graph on the points, edge weights are Manhattan distances, and "all points connected with one simple path between any two" is precisely the MST condition. So the answer is the total weight of the MST.

Prim's idea

Start with one vertex in the tree. Repeatedly pick the cheapest edge crossing from "in-tree" to "out-of-tree" and add the outside endpoint, until every vertex is in.

For dense graphs (like ours, since every pair has an edge), the cleanest implementation uses an array:

• in_mst[v]: whether v is already in the tree.
• min_dist[v]: the cheapest edge from any in-tree vertex to v.

Steps

1. Initialise in_mst = [False] * n, min_dist = [+∞] * n, set min_dist[0] = 0.
2. Run n iterations:
   • Pick the out-of-tree vertex u with the smallest min_dist[u]. (First iteration picks 0.)
   • Add to the answer: cost += min_dist[u]. Mark in_mst[u] = True.
   • Relax neighbours: for every v still out-of-tree, update min_dist[v] = min(min_dist[v], manhattan(u, v)).
3. Return cost.

Walk-through

points = [[0,0], [2,2], [3,10], [5,2], [7,0]]. Indices 0..4.

Pairwise Manhattan matrix (only upper triangle for brevity):

Iter 1: min_dist = [0, ∞, ∞, ∞, ∞]. Pick u = 0 (cheapest). cost = 0. Relax: min_dist = [_, 4, 13, 7, 7].

Iter 2: Pick u = 1 (min_dist[1] = 4). cost = 4. Relax against vertex 1: 1→2=9 (better than 13 → update), 1→3=3 (better than 7 → update), 1→4=7 (tie). min_dist = [_, _, 9, 3, 7].

Iter 3: Pick u = 3 (min_dist[3] = 3). cost = 7. Relax: 3→2=10 (worse), 3→4=4 (better than 7 → update). min_dist = [_, _, 9, _, 4].

Iter 4: Pick u = 4 (min_dist[4] = 4). cost = 11. Relax: 4→2=14 (worse). min_dist = [_, _, 9, _, _].

Iter 5: Pick u = 2 (min_dist[2] = 9). cost = 20.

Final cost: 20. ✓

Why each pick is safe (cut property)

At any moment the tree is a set S and the rest is V - S. The cheapest edge crossing between S and V - S is always in some MST — that's the classic cut property of MSTs. Prim picks exactly that edge each step.

Edge cases

• n == 1: the loop runs once, picks 0, adds cost 0, returns 0.
• Co-linear points (all on one line): the MST is just consecutive nearest neighbours, total = span.

Complexity

• Time: O(n²) — n outer iterations, each scans all n vertices to find the min and to relax.
• Space: O(n) — the two arrays.