1584. Min Cost to Connect All Points

Given points on a 2D plane, the cost of connecting two points is their Manhattan distance. Return the minimum total cost to connect all points (so there is exactly one path between any two).

List all n² edges, sort by length, and add each edge whose endpoints are in different components (union-find), until n − 1 edges are in.

1function minCostConnectPoints(points: number[][]): number {
2  const n = points.length, edges: [number, number, number][] = [];
3  for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++)
4    edges.push([Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]), i, j]);
5  edges.sort((a, b) => a[0] - b[0]);
6  const parent = Array.from({ length: n }, (_, i) => i);
7  const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x])));
8  let total = 0, used = 0;
9  for (const [d, i, j] of edges) {
10    if (used === n - 1) break;
11    const a = find(i), b = find(j);
12    if (a === b) continue;
13    parent[a] = b; total += d; used++;
14  }
15  return total;
16}

total = 0edges = 0

MST so far

edges by length

1–3: 3

0–1: 4

3–4: 4

0–3: 7

0–4: 7

1–4: 7

1–2: 9

2–3: 10

0–2: 13

2–4: 14

Sort all 10 edges by length.

1 / 0

Space: play/pause · ←/→: step