Min Cost to Connect All Points

medium array union find graph mst heap

Problem

Given n points in 2D, the cost to connect two is their Manhattan distance. Return the minimum total cost to connect all points (MST).

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

Output20

Optimal edges total cost 20.

points (JSON)

def min_cost_connect_points(points):
    n = len(points); INF = float('inf')
    dist = [INF] * n; in_mst = [False] * n; dist[0] = 0; total = 0
    for _ in range(n):
        u = -1
        for i in range(n):
            if not in_mst[i] and (u == -1 or dist[i] < dist[u]): u = i
        in_mst[u] = True; total += dist[u]
        for v in range(n):
            if not in_mst[v]:
                d = abs(points[u][0]-points[v][0]) + abs(points[u][1]-points[v][1])
                if d < dist[v]: dist[v] = d
    return total

function minCostConnectPoints(points) {
  const n = points.length;
  const dist = new Array(n).fill(Infinity), inMst = new Array(n).fill(false);
  dist[0] = 0; let total = 0;
  for (let _ = 0; _ < n; _++) {
    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]) {
      const d = Math.abs(points[u][0]-points[v][0]) + Math.abs(points[u][1]-points[v][1]);
      if (d < dist[v]) dist[v] = d;
    }
  }
  return total;
}

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length, total = 0;
        int[] dist = new int[n]; Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] in = new boolean[n]; dist[0] = 0;
        for (int _ = 0; _ < n; _++) {
            int u = -1;
            for (int i = 0; i < n; i++) if (!in[i] && (u == -1 || dist[i] < dist[u])) u = i;
            in[u] = true; total += dist[u];
            for (int v = 0; v < n; v++) if (!in[v]) {
                int d = Math.abs(points[u][0]-points[v][0]) + Math.abs(points[u][1]-points[v][1]);
                if (d < dist[v]) dist[v] = d;
            }
        }
        return total;
    }
}

int minCostConnectPoints(vector>& points) {
    int n = points.size(), total = 0;
    vector dist(n, INT_MAX);
    vector in(n, false); dist[0] = 0;
    for (int _ = 0; _ < n; _++) {
        int u = -1;
        for (int i = 0; i < n; i++) if (!in[i] && (u == -1 || dist[i] < dist[u])) u = i;
        in[u] = true; total += dist[u];
        for (int v = 0; v < n; v++) if (!in[v]) {
            int d = abs(points[u][0]-points[v][0]) + abs(points[u][1]-points[v][1]);
            if (d < dist[v]) dist[v] = d;
        }
    }
    return total;
}

Explanation

We want to connect all points as cheaply as possible — a classic Minimum Spanning Tree (MST). This solution uses Prim's algorithm, which grows the tree one node at a time, always grabbing the cheapest way to attach a new node.

We keep a dist array where dist[v] is the cheapest known cost to connect node v to the tree built so far. We start with dist[0] = 0 and everything else at infinity.

Each round we pick the unattached node u with the smallest dist[u], mark it as in the tree (in_mst[u]), and add its cost to total. Then we look at every node still outside and relax its distance: if the Manhattan distance from u is smaller than its current dist, we update it.

This greedy choice is safe because the cheapest edge crossing from the tree to the outside is always part of some MST.

Example: with points=[[0,0],[2,2],[3,10],[5,2],[7,0]], Prim repeatedly attaches the nearest point, and the cheapest connecting edges sum to 20.

Time: O(n^2) Space: O(n)