Min Cost to Connect All Points

1. Problem & Core Objective

Given n points on a 2-D plane, connect all of them at minimum total cost, where the cost between two points is the Manhattan distance |x1 − x2| + |y1 − y2|. Return the minimum total cost.

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

Constraints: 1 <= n <= 1000 · -10^6 <= x, y <= 10^6 · all points distinct

What's actually being tested: recognising a minimum spanning tree — and noticing that the graph is complete and implicit. There are n(n−1)/2 edges that nobody hands you; you compute distances on demand. That density is what decides Prim's over Kruskal's.

2. First-Principles Thought Process

Why it's an MST

"Connect all points at minimum total cost" is the definition. A spanning tree connects all n nodes with exactly n − 1 edges and no cycles — a cycle would mean a redundant edge you could drop for a lower cost.

The graph is complete and implicit

Any point can connect to any other, so there are n(n−1)/2 edges. At n = 1000 that's about 500,000 — materialising them all is possible but wasteful, and the distance between any pair is a two-line computation.

That density drives the algorithm choice.

Prim's versus Kruskal's

With E ≈ V², Kruskal's O(E log E) is O(V² log V) and requires building and sorting half a million edges. Prim's explores the same edges but never stores them all.

And for a dense graph there's a better Prim's variant: skip the heap entirely and keep a minDist[] array, scanning for the minimum each round. That's O(V²) = 10^6 — faster than O(V² log V) and far simpler.

How Prim's works

Start with any single node. Repeatedly add the cheapest edge connecting the tree to a node outside it, until all n are in.

Why greedy is safe — the cut property

Split the nodes into "in the tree" and "outside". The cheapest edge crossing that cut belongs to some minimum spanning tree.

So taking it never rules out an optimal solution — which is what makes the greedy provably correct rather than merely plausible.

3. Solution Paths

Approach 1 — Kruskal's: build every edge, sort, union-find

public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    List<int[]> edges = new ArrayList<>();                  // {cost, i, j}

    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            edges.add(new int[]{dist(points, i, j), i, j});  // all n(n-1)/2 of them

    edges.sort(Comparator.comparingInt(e -> e[0]));

    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;

    int total = 0, used = 0;
    for (int[] e : edges) {
        if (union(parent, e[1], e[2])) { total += e[0]; if (++used == n - 1) break; }
    }
    return total;
}

private int dist(int[][] p, int i, int j) {
    return Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]);
}

• Time O(V² log V) dominated by the sort · Space O(V²) for the edge list

Counter-questions on this approach

⭐ "It's correct. What's the objection at n = 1000?"

The O(V²) space. Half a million int[3] objects is roughly 20 MB of allocation before any work begins, and sorting them is O(V² log V) ≈ 5 × 10^5 × 19 ≈ 10^7 comparisons.

Prim's explores the same edges but generates each distance on demand and never stores the list. For a dense graph that's the decisive difference.

⭐ "When is Kruskal's the better choice?"

On a sparse graph, where E ≪ V². Then sorting E edges is cheap and union-find is very fast. Kruskal's is also natural when the edges are already given as a list, which they often are.

Here the graph is complete and the edges are implicit, which is exactly the case Prim's is built for. It's worth stating the rule rather than just picking one: Kruskal's for sparse, Prim's for dense.

"Why if (++used == n - 1) break;?"

A spanning tree has exactly n − 1 edges, so once that many unions have succeeded the tree is complete and the remaining edges are all redundant. It's a real saving, since the sorted list is mostly tail.

Approach 2 — Prim's with a heap

public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    boolean[] inTree = new boolean[n];
    PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(e -> e[0]));
    heap.offer(new int[]{0, 0});                     // {cost, node} — start anywhere

    int total = 0, count = 0;
    while (count < n) {
        int[] top = heap.poll();
        int cost = top[0], node = top[1];
        if (inTree[node]) continue;                   // stale entry — already connected

        inTree[node] = true;
        total += cost;
        count++;

        for (int next = 0; next < n; next++)          // every other point is a neighbour
            if (!inTree[next]) heap.offer(new int[]{dist(points, node, next), next});
    }
    return total;
}

• Time O(V² log V) · Space O(V²) heap entries in the worst case

Counter-questions on this approach

⭐ "Why the if (inTree[node]) continue; check?"

Because the heap accumulates stale entries. A node can be offered many times — once from each tree node that considers it — and only the first pop is the cheapest. Later pops for the same node are obsolete.

This is lazy deletion: rather than removing outdated entries (which a heap can't do cheaply — remove(Object) is O(n)), leave them and skip them on arrival. Standard for heap-based Dijkstra and Prim's alike.

⭐ "How many entries can the heap hold?"

Up to O(V²) — each of V tree additions offers up to V neighbours. So at n = 1000 that's potentially 10^6 entries, which is the same memory problem as Kruskal's edge list.

That's the argument for the array-based variant below, which holds O(V).

"Why start at node 0 with cost 0?"

An MST spans all nodes, so any starting point produces the same total cost. Seeding with cost 0 means the first pop adds node 0 for free, which is correct — the first node joins the tree without an edge.

Approach 3 — Prim's with a minDist[] array (optimal for dense graphs)

public int minCostConnectPoints(int[][] points) {
    int n = points.length;
    boolean[] inTree = new boolean[n];
    int[] minDist = new int[n];
    Arrays.fill(minDist, Integer.MAX_VALUE);
    minDist[0] = 0;                                    // start at node 0

    int total = 0;
    for (int iter = 0; iter < n; iter++) {
        int best = -1;
        for (int i = 0; i < n; i++)                    // scan for the cheapest outside node
            if (!inTree[i] && (best == -1 || minDist[i] < minDist[best])) best = i;

        inTree[best] = true;
        total += minDist[best];

        for (int i = 0; i < n; i++)                    // relax: is `best` a cheaper connection?
            if (!inTree[i]) minDist[i] = Math.min(minDist[i], dist(points, best, i));
    }
    return total;
}

Trace — points = [[0,0],[2,2],[3,10],[5,2],[7,0]]:

Total 0 + 4 + 3 + 4 + 9 = 20 ✓

• Time O(V²) · Space O(V)

Counter-questions on this approach

⭐ "No heap at all. Why is O(V²) better than O(V² log V) here?"

Because the graph is complete. The heap's advantage is skipping edges you never examine — but here every pair is an edge, so nothing is skipped and the log factor is pure overhead.

O(V²) = 10^6 operations with tiny constants, versus O(V² log V) ≈ 10^7 with heap operations and object allocation. And space drops from O(V²) to O(V).

The rule: heap-based Prim's for sparse graphs, array-based for dense ones. This graph is maximally dense.

⭐ "What does minDist[i] actually mean?"

The cheapest edge connecting node i to any node already in the tree — not its distance from the start. It's the cost i would pay to join right now.

After adding a node, every outside node's minDist is relaxed against the new tree member, since it may offer a cheaper connection. That relaxation is O(V) per round, giving O(V²) overall.

⭐ "Why is greedy correct here at all?"

The cut property: partition the nodes into those in the tree and those outside. The cheapest edge crossing that cut is in some MST.

Proof sketch: suppose an MST T omits the cheapest crossing edge e. Adding e to T creates a cycle, which must contain another edge f crossing the same cut. Since e is the cheapest crossing edge, cost(e) <= cost(f), so swapping f for e gives a spanning tree no more expensive. So an MST containing e exists.

That's why the greedy never needs to reconsider — it's an exchange argument, not a heuristic.

"Could the total overflow int?"

Coordinates reach 10^6, so a single Manhattan distance is at most 4 × 10^6. With n − 1 = 999 edges the total is at most 4 × 10^9 — which exceeds Integer.MAX_VALUE of about 2.1 × 10^9.

In practice an MST's edges are far shorter than the maximum, so it passes. But it's close enough that I'd check rather than assume, and I'd use a long accumulator if the bound were any looser.

"Why does the loop run exactly n times?"

Each iteration adds exactly one node to the tree, and there are n nodes. The first adds node 0 at cost 0, so the total counts n − 1 real edges — which is the spanning tree's edge count.

Comparison

4. Why the Optimal Wins

All three compute the same MST. The difference is whether you materialise the edges.

Kruskal's must build and sort all n(n−1)/2 of them — 500,000 objects at n = 1000. Heap-based Prim's avoids the sort but still queues up to O(V²) entries.

Array-based Prim's holds O(V) state and computes distances on demand, and on a complete graph the heap's selectivity buys nothing — so dropping it removes the log factor outright.

The framing worth keeping:

"Connect everything at minimum cost" is an MST. When the graph is complete and implicit, use Prim's with a minDist[] array: O(V²) time, O(V) space, and no edge list at all. Kruskal's is for sparse graphs.

And the correctness guarantee: the cut property makes the greedy provably optimal, not merely plausible.

5. Java Prerequisites

Manhattan distance

Math.abs(p[i][0] - p[j][0]) + Math.abs(p[i][1] - p[j][1]);

No square root — unlike Euclidean distance, this is exact in integers.

Array-based Prim's

int[] minDist = new int[n];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[0] = 0;
// each round: pick the cheapest outside node, add it, relax all others against it

Lazy deletion in the heap version

if (inTree[node]) continue;      // stale entry; the first pop was the real one

PriorityQueue.remove(Object) is O(n), which is why stale entries are skipped rather than removed.

Overflow check — distances up to 4 × 10^6 times 999 edges approaches int range. Use long if the bound is looser.

6. Interview Communication Guide

Clarifying questions: Is the distance Manhattan or Euclidean (Manhattan — no square root, stays integral)? Can points repeat (no, all distinct)? What's n (1000 — which makes the graph dense and drives the algorithm choice)? Do I need the edges themselves or just the total (just the total)?

The pitch

"'Connect all points at minimum total cost' is a minimum spanning tree — n − 1 edges, no cycles, since any cycle would contain a redundant edge.

The important observation is that the graph is complete and implicit. Every point can connect to every other, so there are about half a million edges at n = 1000, and nobody hands them to me — each distance is a two-line computation.

That density decides the algorithm. Kruskal's would have to build and sort all n(n−1)/2 edges — 500,000 objects, roughly 20 MB, before any work. It's the right choice for a sparse graph or when the edges are already given.

Prim's grows a single tree, always taking the cheapest edge leaving it, and never needs the edge list.

And because the graph is maximally dense, I'd skip the heap entirely and use a minDist[] array — where minDist[i] is the cheapest edge connecting i to anything already in the tree. Each round: scan for the cheapest outside node, add it, then relax every remaining node against the new member. That's O(V²) = 10^6 with tiny constants, versus O(V² log V) with heap allocation. Space drops from O(V²) to O(V).

The heap only helps when it lets you skip edges — on a complete graph nothing is skipped, so the log is pure overhead.

The greedy is provably correct by the cut property: split the nodes into in-tree and outside, and the cheapest edge crossing that cut is in some MST. So taking it can never rule out an optimum.

One thing I'd check: coordinates reach 10^6, so a single distance is up to 4 × 10^6, and 999 of those would exceed int. Real MSTs are far below that, but it's close enough to verify rather than assume."

Edge cases to volunteer:

Name the single-point case. It must return 0 — the loop runs once, adds node 0 at its seeded cost of 0, and there's no edge. A solution that assumes n − 1 edges exist would break.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the edges of the MST, not just the cost."

Track, alongside minDist[i], which tree node offered that distance — a parent[] array updated during relaxation. Then the MST edges are (parent[i], i) for every i except the start. O(V) extra space, no complexity change.

⭐ "Use Euclidean distance instead."

The algorithm is unchanged, but distances become floating point. Compare squared distances to stay in integers where possible — though the sum of square roots can't be avoided if the total cost is required, so the accumulator must be double.

"What if some pairs couldn't be connected?"

The graph stops being complete. Then it's sparse, Kruskal's becomes competitive, and you must check the result actually spans — if fewer than n − 1 edges are usable, no spanning tree exists.

"What if n were 10^5?"

O(V²) = 10^10 — infeasible. A complete graph on 10^5 points has 5 × 10^9 edges, so no MST algorithm on the explicit graph works. For Manhattan distance specifically there's a classical result: only O(n) candidate edges matter (the nearest neighbour in each of 8 octants), reducing it to a sparse graph plus Kruskal's at O(n log n).

"Find the maximum spanning tree instead."

Negate the weights, or take the largest crossing edge each round. The cut property holds symmetrically.

"What if edges could be added later and you re-queried the MST?"

A new cheap edge might improve the tree. Adding edge (u,v) creates a cycle in the MST; if the new edge is cheaper than the heaviest edge on that cycle, swap them. O(V) per update with the tree stored, versus O(V²) to recompute.