Min Cost to Connect All Points

Examples

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

One cheapest way connects the points in a tree using edges totaling 20, rather than paying for every possible pairwise connection.

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

Connecting (-4,1)-(-2,5) costs 6, and (-2,5)-(3,12) costs 12, for a total of 18 - cheaper than any other way to link all three points.

Input: points = [[0,0],[1,1],[1,0],[0,1]]
Output: 3

These four points form a unit square where every side (but not the diagonals) costs 1 to connect; a spanning tree needs only 3 of those unit-cost sides, for a total of 3.

Constraints

• 1 <= points.length <= 1000

• -10^6 <= xi, yi <= 10^6

• All pairs of points are distinct.

Approach

This is asking for a Minimum Spanning Tree (MST): pick a subset of connections, of minimum total cost, that links every point into one connected group, using exactly n - 1 connections for n points (any spanning tree with a valid cycle-free structure has exactly that many edges).

Since every pair of points can be directly connected, this is really an MST over a complete graph, where the edge weight between any two points is their Manhattan distance.

Two classic MST algorithms apply. Kruskal's algorithm builds the full list of n * (n - 1) / 2 possible edges, sorts them by cost, and greedily adds each edge (using a union-find structure to skip edges that would form a cycle) until all points are connected. Prim's algorithm instead grows a single tree from one starting point, repeatedly adding the cheapest edge connecting the current tree to any point outside of it - this avoids ever materializing the full edge list, which matters more as n grows.

Solutions

Kruskal's Algorithm - Sort Edges + Union-Find

Build every possible edge between pairs of points along with its Manhattan-distance cost, then sort all edges from cheapest to most expensive. Walk through the sorted edges and greedily add each one to the growing spanning tree, unless its two endpoints are already connected (adding it would create a useless cycle). A union-find (disjoint set) structure answers "are these two points already connected?" and merges groups quickly. Stop once n - 1 edges have been added - the tree now spans every point.

function minCostConnectPoints(points) {
  const n = points.length;
  const edges = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const cost = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
      edges.push([cost, i, j]);
    }
  }
  edges.sort((a, b) => a[0] - b[0]);

  const parent = Array.from({ length: n }, (_, i) => i);
  function find(x) {
    while (parent[x] !== x) {
      parent[x] = parent[parent[x]];
      x = parent[x];
    }
    return x;
  }

  let totalCost = 0;
  let edgesUsed = 0;
  for (const [cost, i, j] of edges) {
    const rootI = find(i);
    const rootJ = find(j);
    if (rootI === rootJ) continue;
    parent[rootI] = rootJ;
    totalCost += cost;
    edgesUsed++;
    if (edgesUsed === n - 1) break;
  }

  return totalCost;
}

Time: O(n^2 log n), dominated by sorting the O(n^2) candidate edges · Space: O(n^2) to store every candidate edge

Optimal - Prim's Algorithm

Start a tree with just one point. Keep an array minCost recording, for every point not yet in the tree, the cheapest cost seen so far to connect it directly to some point already in the tree (initialized to infinity, except the starting point). Repeatedly pick the not-yet-included point with the smallest minCost, add it to the tree, add its cost to the running total, and then update minCost for every remaining point based on its distance to the point that was just added. After n points have been added this way, every point is connected and the running total is the MST cost. This never needs to build or sort the full O(n^2) edge list.

function minCostConnectPoints(points) {
  const n = points.length;
  const inTree = new Array(n).fill(false);
  const minCost = new Array(n).fill(Infinity);
  minCost[0] = 0;

  let totalCost = 0;

  for (let added = 0; added < n; added++) {
    let u = -1;
    for (let i = 0; i < n; i++) {
      if (!inTree[i] && (u === -1 || minCost[i] < minCost[u])) {
        u = i;
      }
    }

    inTree[u] = true;
    totalCost += minCost[u];

    for (let v = 0; v < n; v++) {
      if (inTree[v]) continue;
      const cost = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
      if (cost < minCost[v]) {
        minCost[v] = cost;
      }
    }
  }

  return totalCost;
}

Time: O(n^2), since each of the n rounds scans all n points to pick the next one and to update costs · Space: O(n) for the minCost and inTree arrays