8.7 Minimum Spanning Tree (MST)

Demo: Min Cost to Connect All Points — LC 1584 (Medium — Google/Amazon High)

Statement (Demo): Given points on a 2D plane, return the minimum cost to connect all of them, where connecting two points costs their Manhattan distance. Example: points=[[0,0],[2,2],[3,10],[5,2],[7,0]] → 20 | ⚡ n ≤ 1000

Approach: Prim's — for every node outside the MST, track its cheapest cost to join. Each step, add the cheapest one and update the others' costs. The graph is dense (an edge between every pair), so an O(n²) scan beats a heap.

function minCostConnectPoints(points) {
  const n = points.length;
  const dist = new Array(n).fill(Infinity); // cost to join the MST
  const inMST = new Array(n).fill(false);
  dist[0] = 0;
  let total = 0;
  for (let step = 0; step < n; step++) {
    let u = -1;
    for (let i = 0; i < n; i++)
      if (!inMST[i] && (u === -1 || dist[i] < dist[u])) u = i;
    inMST[u] = true;
    total += dist[u];
    for (let v = 0; v < n; v++) {
      if (inMST[v]) continue;
      const d =
        Math.abs(points[u][0] - points[v][0]) +
        Math.abs(points[u][1] - points[v][1]);
      dist[v] = Math.min(dist[v], d);
    }
  }
  return total;
}

Complexity: Time O(n²), Space O(n)