Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumminimum-spanning-tree

Min Cost to Connect All Points

Problem (restated)

Points on the plane. Cost of an edge is Manhattan |x1-x2| + |y1-y2|. Return the MST weight connecting all points.

Intuition

Complete graph, n ≤ 1000 so n² edges are fine. Generate every pair, Kruskal.

Approaches

Kruskal, Manhattan

Unverified

Time O(n² log n)Space O(n²)

Idea. For i < j, push (i, j, manhattan). Sort, union until n-1 edges.

Walkthrough. [[0,0],[2,2],[3,10],[5,2],[7,0]] → 20.

Trade-offs. Prim from one seed with a dense O(n²) scan avoids storing all edges; Kruskal is the template and is simpler. Points are 0-indexed.

Solution

export function minCostConnectPoints(points: number[][]): number {
  const n = points.length;
  const edges: [number, number, number][] = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const w = Math.abs(points[i]![0]! - points[j]![0]!) + Math.abs(points[i]![1]! - points[j]![1]!);
      edges.push([i, j, w]);
    }
  }
  edges.sort((a, b) => a[2] - b[2]);
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const [u, v, w] of edges) {
    const a = find(u), b = find(v);
    if (a === b) continue;
    parent[a] = b;
    cost += w;
    used++;
    if (used === n - 1) break;
  }
  return cost;
}

export function minCostConnectPoints(points: number[][]): number {
  const n = points.length;
  const edges: [number, number, number][] = [];
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const w = Math.abs(points[i]![0]! - points[j]![0]!) + Math.abs(points[i]![1]! - points[j]![1]!);
      edges.push([i, j, w]);
    }
  }
  edges.sort((a, b) => a[2] - b[2]);
  const parent = Array.from({ length: n }, (_, i) => i);
  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
  let cost = 0, used = 0;
  for (const [u, v, w] of edges) {
    const a = find(u), b = find(v);
    if (a === b) continue;
    parent[a] = b;
    cost += w;
    used++;
    if (used === n - 1) break;
  }
  return cost;
}

Template connection

Kruskal after you materialize the complete graph. Same as LC 1135 with a generated edge list.

Reflection

The cost is Manhattan. Every pair is an edge. Kruskal keeps n - 1 of them. Prim reaches the same total.
n = 1 answers 0. Two equal points cost 0. A negative coordinate is fine because the distance uses the absolute value.
There are on the order of n**2 edges. The sort decides which costs win. An edge that closes a cycle is skipped.