medium

Min Cost to Connect All Points

Find the cheapest way to connect every point on a plane using straight-line connections.

1. Define the problem

Min Cost to Connect All Points

You are given an array points where pointsi = [xi, yi] represents a point on the 2D plane. The cost to connect two points is the Manhattan distance between them: |xi - xj| + |yi - yj|. Return the minimum cost to connect all points so that every point is reachable from every other point, directly or through other points. Treat every pair of points as a weighted edge, sort those edges by cost, and run Kruskal's algorithm with union-find to build the minimum spanning tree.

Constraints

  • 1 ≤ points.length ≤ 1000
  • -106 ≤ xi, yi ≤ 106
  • All pairs (xi, yi) are distinct

Example

Inputpoints = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output20

Explanation The minimum spanning tree uses the edges P1–P3 (3), P0–P1 (4), P3–P4 (4), and P1–P2 (9), for a total cost of 20.

2. Know the words first

In plain terms

Manhattan distance
The distance between two points measured along the axes, like walking city blocks instead of cutting diagonally — |x1 - x2| + |y1 - y2|.
Minimum spanning tree
The cheapest possible set of edges that connects every point with no cycles.
3. Visualize the solution

Sort every pairwise distance, then greedily accept unless it cycles

Sort every pairwise distance, then greedily accept unless it cycles
Statusedge 1/7

P1–P3 costs 3, the cheapest edge. Different points — accept. Total so far: 3.

What happens in this step

edge P1–P3, w=3 (cheapest of the 10 pairwise edges)
find(P1)=P1, find(P3)=P3 → different roots
accept, union(P1, P3)

MST cost so far = 3
Step 1 of 7

Steps to visualize

  1. Build one edge per pair of points, weighted by Manhattan distance.
  2. Sort every edge from cheapest to priciest.
  3. Walk the sorted edges once, accepting an edge unless its two points are already connected.
  4. Stop once n - 1 edges have been accepted — every point is now reachable from every other.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Sort every pairwise distance, then greedily accept unless it cycles
Statusedge 1/7

P1–P3 costs 3, the cheapest edge. Different points — accept. Total so far: 3.

What happens in this step

edge P1–P3, w=3 (cheapest of the 10 pairwise edges)
find(P1)=P1, find(P3)=P3 → different roots
accept, union(P1, P3)

MST cost so far = 3
Step 1 of 7
5. Solution

Solution

solution.tsTypeScript
function minCostConnectPoints(points) {
  const n = points.length;
  if (n <= 1) return 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;
  }

  function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA === rootB) return false;
    parent[rootA] = rootB;
    return true;
  }

  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]);

  let total = 0;
  let edgesUsed = 0;
  for (const [cost, a, b] of edges) {
    if (union(a, b)) {
      total += cost;
      edgesUsed++;
      if (edgesUsed === n - 1) break;
    }
  }

  return total;
}
Time
O(n² log n)
Space
O(n²)
6. Test cases

Test cases

InputExpectedCovers
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]20example from the docstring
points = [[0,0],[1,1]]2smallest non-trivial case, a single edge
points = [[5,5]]0a single point needs no edges at all
points = [[0,0],[1,0],[2,0],[3,0]]3points already in a line — the obvious chain is the MST
points = [[0,0],[0,2],[2,0],[2,2]]6a square with several equal-weight edges — ties in the sort must still build a valid tree
points = [[-1,-1],[1,1],[-1,1],[1,-1]]6negative coordinates mixed with positive ones
points = [[0,0],[0,1],[1,0]]2a small triangle where the most expensive edge must be rejected

Keep reading