Minimum Cost to Connect All Points — Prim's MST on a Complete Graph [LC 1584, Amazon, Google]

Problem Statement#

Given an array points where points[i] = [xi, yi] represents a point on a 2D plane, return the minimum cost to make all points connected. The cost of connecting two points (xi, yi) and (xj, yj) is the Manhattan distance |xi - xj| + |yi - yj|. All points are connected if there is exactly one simple path between any two points.

Constraints:

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

Example 1:

Input:  points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20
Explanation: Connecting the points in a tree shape with edges of weight
0-1 (4), 1-3 (3), 1-2 (9), 3-4 (4) yields total cost 20 — minimum spanning tree.

Example 2:

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

Why This Problem Matters#

LeetCode 1584 Minimum Cost to Connect All Points is the canonical FAANG question that hides a classic Minimum Spanning Tree problem behind innocent-looking geometry. Amazon, Google, Meta, and Uber all ask variants because solving it correctly tests three layered skills at once: recognising MST under disguise, choosing between Prim's and Kruskal's based on edge density, and implementing a heap- or array-based Prim that avoids materialising the full O(n^2) edge list.

In real systems, this is the algorithm behind laying telecom backbone fibre, planning road grids for new neighbourhoods, designing minimum-wire layouts on PCBs, and provisioning the cheapest set of links connecting data centres. Whenever the prompt mentions "connect everything with the smallest total cost," the answer is almost always MST. Internalising the pattern shaves entire interview rounds because once the MST disguise is lifted, the remaining work is pure muscle memory.

The trick that separates a 30-minute solution from a clean 10-minute one is realising that with n <= 1000 we have up to n^2 ~ 10^6 implicit edges. Building an explicit edge list and running Kruskal's is correct but wasteful. Prim's on a dense graph using an array-based key (or a lazy heap) runs in O(n^2) time and O(n) extra space — strictly better for this constraint range.

The Core Insight#

The points and pairwise Manhattan distances form a complete weighted undirected graph K_n with n*(n-1)/2 edges. We need the cheapest spanning subgraph that touches every vertex — by definition, the Minimum Spanning Tree.

Two MST algorithms apply, with very different ergonomics:

• Prim's algorithm (best here): grow a tree from one seed vertex, repeatedly adding the cheapest edge that touches a new vertex. Runs in O(V^2) with an array-based key, which beats O(E log V) = O(V^2 log V) for dense graphs.
• Kruskal's algorithm: sort all O(n^2) edges, then union-find them in order. Runs in O(n^2 log n). Correct but slower and uses more memory because we have to materialise the edge list.

The Prim's invariant is simple: maintain key[v] = the minimum cost to attach vertex v to the partial tree built so far. On each iteration, pick the unvisited vertex u with smallest key[u], mark it visited, add key[u] to the running total, and relax its neighbours by key[v] = min(key[v], dist(u, v)).

For dense graphs, the array variant is preferred because both the "extract-min" and the "decrease-key" steps cost O(n), giving an overall O(n^2). With a heap you pay O(log n) per edge but you also pay for n^2 insertions, so the heap variant is O(n^2 log n) — worse, not better.

Visual Dry Run#

points = [[0,0], [2,2], [3,10], [5,2], [7,0]]. Run Prim's starting from vertex 0.

Final answer: 20. Notice we never built the edge list — key[v] is recomputed lazily by scanning unvisited vertices each round.

Solution (Optimal)#

Python — Prim's O(n^2) with array-based key#

def minCostConnectPoints(points):
    n = len(points)
    in_mst = [False] * n
    key = [float('inf')] * n
    key[0] = 0
    total = 0
 
    for _ in range(n):
        # extract-min over unvisited
        u = -1
        for v in range(n):
            if not in_mst[v] and (u == -1 or key[v] < key[u]):
                u = v
        in_mst[u] = True
        total += key[u]
 
        # relax neighbours
        xu, yu = points[u]
        for v in range(n):
            if not in_mst[v]:
                d = abs(xu - points[v][0]) + abs(yu - points[v][1])
                if d < key[v]:
                    key[v] = d
    return total

JavaScript — Prim's O(n^2)#

function minCostConnectPoints(points) {
    const n = points.length;
    const inMST = new Array(n).fill(false);
    const key = new Array(n).fill(Infinity);
    key[0] = 0;
    let total = 0;
 
    for (let i = 0; i < n; i++) {
        let u = -1;
        for (let v = 0; v < n; v++) {
            if (!inMST[v] && (u === -1 || key[v] < key[u])) u = v;
        }
        inMST[u] = true;
        total += key[u];
        for (let v = 0; v < n; v++) {
            if (!inMST[v]) {
                const d = Math.abs(points[u][0] - points[v][0]) +
                          Math.abs(points[u][1] - points[v][1]);
                if (d < key[v]) key[v] = d;
            }
        }
    }
    return total;
}

Complexity#

For n = 1000, the array Prim runs in about 10^6 operations — well under a second.

Common Mistakes#

• Building all n^2 edges first. Wastes memory and pushes you into the O(n^2 log n) regime unnecessarily.
• Using a heap-based Prim on a dense graph. Looks elegant but the heap holds O(n^2) stale entries, blowing up runtime and memory.
• Forgetting Manhattan vs Euclidean distance. The problem explicitly uses Manhattan; using sqrt produces the wrong answer and floating-point drift.
• Restarting Prim's from every vertex. MST is a global structure; one seed is enough because the MST is unique up to ties on a connected graph.
• Returning the count of edges instead of the sum of weights. The answer is the total cost, not the number of edges (which is always n - 1).

Interview Tips#

• Open with: "This is a Minimum Spanning Tree problem on a complete graph with n*(n-1)/2 Manhattan-distance edges." Naming the abstraction earns immediate points.
• Justify Prim over Kruskal by counting edges: "With n = 1000, we have up to a million edges. Array-based Prim is O(n^2), Kruskal is O(n^2 log n)."
• If the interviewer pushes back, mention that for sparse graphs Kruskal with union-find is preferable.
• Mention Manhattan-distance MST has an O(n log n) algorithm using sweep line plus nearest-neighbour structures (Guibas-Stolfi). Most interviewers will not require it but knowing it signals depth.
• Watch for off-by-one bugs in the extract-min loop — initialise u = -1 and guard against picking visited vertices.

Follow-up Questions#

• What if distances are Euclidean? Same algorithm; replace abs(dx) + abs(dy) with sqrt(dx*dx + dy*dy). Sometimes interviewers ask you to keep it integer using squared distances — only safe if all you compare are squared values.
• What if you need the actual edges, not just the total cost? Track parent[v] alongside key[v]. Each pick produces an edge parent[u] - u.
• Can you do better than O(n^2)? For Manhattan, yes — using L1 Voronoi or rotated coordinates you can build a candidate edge set of size O(n) and run Kruskal in O(n log n).
• What if a few edges already exist with cost 0 (pre-connected)? Pre-set key[v] = 0 for those vertices or run Kruskal with the freebies inserted first.

Key Takeaways#

• LeetCode 1584 is a Minimum Spanning Tree problem disguised as geometry — recognise the pattern immediately.
• Prefer array-based Prim's O(n^2) over heap-based Prim or Kruskal for dense graphs with up to 1000 vertices.
• Never materialise the full O(n^2) edge list when the cost can be computed lazily inside the relax loop.
• The MST invariant — key[v] = best known cost to attach v — is the heart of every Prim variant.
• This pattern applies to telecom backbone, road planning, PCB routing, and any "connect all nodes cheaply" problem in production.
• Companies that ask this: Amazon, Google, Meta, Uber, Bloomberg, ByteDance, Microsoft.