Min Cost to Connect All Points

You have some points on a map. You want to connect them all with wires so every point can reach every other point. Wires cost money based on length. So you want the cheapest set of wires. This is a classic minimum spanning tree question. Interviewers love it because it tests whether you know that famous pattern.

🎯 The Problem

You get a list of points. You must connect them all for the smallest total cost.

The rules:

• Each point is [x, y].
• The cost to connect two points is their Manhattan distance. That means you add the gap in x and the gap in y. For (a, b) and (c, d) it is |a - c| + |b - d|.
• Connect all points so there is a path between any two of them.
• Return the smallest total cost.

Input:  points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output: 20

Explanation: Connecting all five points with the cheapest set of wires
costs 20 in total.

A set of wires that links everything with no wasted loop is called a spanning tree. The cheapest such set is the minimum spanning tree, or MST. Here is the full graph of possible wires between the points, with a few example costs.

🐢 Approach 1: Try Every Set of Wires (Brute Force)

The idea in one line: list every way to connect all points and keep the cheapest.

The idea:

• A connecting set of wires with no wasted loop is a spanning tree.
• Generate every possible spanning tree.
• Add up the cost of each one and keep the smallest total.

Why it is weak:

• The number of spanning trees explodes as points grow.
• For just a handful of points you already have far too many to list.
• This is not practical past tiny inputs.

Here is an exhaustive edge-subset sketch:

from itertools import combinations
def min_cost_connect_points(points):
    n = len(points)
    edges = [(abs(a[0]-b[0]) + abs(a[1]-b[1]), i, j) for i, a in enumerate(points) for j, b in enumerate(points) if i < j]
    best = float("inf")
    for subset in combinations(edges, n - 1):
        parent = list(range(n))
        def find(x):
            while parent[x] != x: x = parent[x]
            return x
        for w, a, b in subset: parent[find(a)] = find(b)
        if len({find(i) for i in range(n)}) == 1:
            best = min(best, sum(w for w, a, b in subset))
    return best

🌲 Approach 2: Kruskal’s Algorithm (Better)

The idea in one line: sort every possible wire by cost, then add the cheap ones that do not form a loop.

The idea:

• Kruskal’s algorithm looks at edges, not points.
• It always grabs the cheapest wire that does not close a cycle.

How it works:

• List every wire between every pair of points with its cost.
• Sort all the wires from cheapest to most expensive.
• Walk the sorted list. Add a wire if its two points are not already connected.
• Use union-find to check if two points already share a group.
• Stop once every point is connected.

Why it is weak here:

• Every point connects to every other point. So there are about n² wires.
• Sorting all of them costs O(n² log n).
• That sort is the slow part on a dense graph.

Here is Kruskal’s algorithm:

def min_cost_connect_points(points):
    n = len(points); parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]; x = parent[x]
        return x
    edges = sorted((abs(a[0]-b[0]) + abs(a[1]-b[1]), i, j) for i, a in enumerate(points) for j, b in enumerate(points) if i < j)
    cost = used = 0
    for w, a, b in edges:
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb; cost += w; used += 1
            if used == n - 1: break
    return cost

⚡ Approach 3: Prim’s Algorithm (Best)

The idea in one line: grow one tree outward, always pulling in the nearest point not yet inside.

The idea:

• Prim’s algorithm grows the tree one point at a time.
• It always adds the cheapest wire that reaches a point still outside.
• This is a greedy method. Greedy means take the best local step now and trust it.

How it works:

• Start with any one point inside the tree.
• Keep the cheapest known cost to reach each outside point.
• Pick the outside point with the smallest cost. Pull it in. Add that cost to the total.
• After pulling a point in, update the costs of the remaining outside points. The new point may offer a cheaper wire.
• Repeat until every point is inside.

Why it is fast here:

• The simple array version is O(n²), no sorting needed.
• A dense graph already has about n² wires, so O(n²) is a natural fit.
• It uses only two small arrays, so the memory is small.

Here is how Prim’s grows the tree on the example. Each step pulls in the cheapest reachable point and adds its wire cost.

Steps to Solve

1. Put the first point into the tree. Set its cost to zero and all other costs to a large number.
2. Track which points are already inside the tree.
3. Find the outside point with the smallest cost to reach.
4. Add that point to the tree and add its cost to the total.
5. For each remaining outside point, update its cost using the Manhattan distance to the point just added, if that is cheaper.
6. Repeat until all points are inside the tree, then return the total.

#include <stdio.h>
#include <stdlib.h>

int absInt(int x) { return x < 0 ? -x : x; }

int minCostConnect(int points[][2], int n) {
    int minCost[100];
    int inTree[100];
    for (int i = 0; i < n; i++) { minCost[i] = 1000000000; inTree[i] = 0; }
    minCost[0] = 0;  // start from point 0

    int total = 0;
    for (int c = 0; c < n; c++) {
        int u = -1;
        for (int i = 0; i < n; i++) {          // cheapest outside point
            if (!inTree[i] && (u == -1 || minCost[i] < minCost[u])) u = i;
        }
        inTree[u] = 1;
        total += minCost[u];
        for (int v = 0; v < n; v++) {          // update neighbors
            if (!inTree[v]) {
                int d = absInt(points[u][0] - points[v][0]) +
                        absInt(points[u][1] - points[v][1]);
                if (d < minCost[v]) minCost[v] = d;
            }
        }
    }
    return total;
}

int main(void) {
    int points[][2] = {{0,0},{2,2},{3,10},{5,2},{7,0}};
    int n = 5;
    printf("%d\n", minCostConnect(points, n));
    return 0;
}

20

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

int minCostConnect(vector<vector<int>>& points) {
    int n = points.size();
    vector<int> minCost(n, INT_MAX);
    vector<bool> inTree(n, false);
    minCost[0] = 0;  // start from point 0

    int total = 0;
    for (int c = 0; c < n; c++) {
        int u = -1;
        for (int i = 0; i < n; i++) {           // cheapest outside point
            if (!inTree[i] && (u == -1 || minCost[i] < minCost[u])) u = i;
        }
        inTree[u] = true;
        total += minCost[u];
        for (int v = 0; v < n; v++) {           // update neighbors
            if (!inTree[v]) {
                int d = abs(points[u][0] - points[v][0]) +
                        abs(points[u][1] - points[v][1]);
                minCost[v] = min(minCost[v], d);
            }
        }
    }
    return total;
}

int main() {
    vector<vector<int>> points = {{0,0},{2,2},{3,10},{5,2},{7,0}};
    cout << minCostConnect(points) << endl;
    return 0;
}

20

public class Connect {
    public static int minCostConnect(int[][] points) {
        int n = points.length;
        int[] minCost = new int[n];
        boolean[] inTree = new boolean[n];
        for (int i = 0; i < n; i++) minCost[i] = Integer.MAX_VALUE;
        minCost[0] = 0;  // start from point 0

        int total = 0;
        for (int c = 0; c < n; c++) {
            int u = -1;
            for (int i = 0; i < n; i++) {        // cheapest outside point
                if (!inTree[i] && (u == -1 || minCost[i] < minCost[u])) u = i;
            }
            inTree[u] = true;
            total += minCost[u];
            for (int v = 0; v < n; v++) {        // update neighbors
                if (!inTree[v]) {
                    int d = Math.abs(points[u][0] - points[v][0]) +
                            Math.abs(points[u][1] - points[v][1]);
                    minCost[v] = Math.min(minCost[v], d);
                }
            }
        }
        return total;
    }

    public static void main(String[] args) {
        int[][] points = {{0,0},{2,2},{3,10},{5,2},{7,0}};
        System.out.println(minCostConnect(points));
    }
}

20

def min_cost_connect(points):
    n = len(points)
    min_cost = [float("inf")] * n
    in_tree = [False] * n
    min_cost[0] = 0          # start from point 0

    total = 0
    for _ in range(n):
        # pick the cheapest point not yet in the tree
        u = -1
        for i in range(n):
            if not in_tree[i] and (u == -1 or min_cost[i] < min_cost[u]):
                u = i
        in_tree[u] = True
        total += min_cost[u]
        # update the cost to reach each remaining point
        for v in range(n):
            if not in_tree[v]:
                d = abs(points[u][0] - points[v][0]) + \
                    abs(points[u][1] - points[v][1])
                if d < min_cost[v]:
                    min_cost[v] = d
    return total


points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]
print(min_cost_connect(points))

20

function minCostConnect(points) {
  const n = points.length;
  const minCost = new Array(n).fill(Infinity);
  const inTree = new Array(n).fill(false);
  minCost[0] = 0; // start from point 0

  let total = 0;
  for (let c = 0; c < n; c++) {
    let u = -1;
    for (let i = 0; i < n; i++) {        // cheapest outside point
      if (!inTree[i] && (u === -1 || minCost[i] < minCost[u])) u = i;
    }
    inTree[u] = true;
    total += minCost[u];
    for (let v = 0; v < n; v++) {        // update neighbors
      if (!inTree[v]) {
        const d = Math.abs(points[u][0] - points[v][0]) +
                  Math.abs(points[u][1] - points[v][1]);
        if (d < minCost[v]) minCost[v] = d;
      }
    }
  }
  return total;
}

const points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]];
console.log(minCostConnect(points));

20

Let us read the Python version line by line and see the reason for each piece.

min_cost = [float("inf")] * n
in_tree = [False] * n
min_cost[0] = 0

min_cost[i] holds the cheapest known wire that reaches point i from the growing tree. We start every point as infinity because we do not yet know any wire. in_tree marks which points are already connected. We set min_cost[0] to zero so the very first point we pull in costs nothing. That is just our starting seed.

u = -1
for i in range(n):
    if not in_tree[i] and (u == -1 or min_cost[i] < min_cost[u]):
        u = i

This loop scans all outside points and keeps the one with the smallest cost. That point u is the cheapest way to grow the tree right now. This greedy pick is the core of Prim’s algorithm.

in_tree[u] = True
total += min_cost[u]

We pull u into the tree and pay its wire cost. Once a point is in the tree, we never pay for it again.

for v in range(n):
    if not in_tree[v]:
        d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])
        if d < min_cost[v]:
            min_cost[v] = d

Now that u is inside, it may offer a cheaper wire to some outside point v. So we compute the Manhattan distance from u to each outside v and lower min_cost[v] if this new wire is cheaper. This keeps every outside point’s cost honest for the next round.

⏱️ Time and Space Complexity

This dense version of Prim’s algorithm checks every pair of points across the rounds. So the time is O(n²), where n is the number of points. That is good here because every point already connects to every other point, so there are about n² possible wires anyway. The space is O(n) for the cost and flag arrays. Kruskal’s algorithm would need to sort all n² wires, which costs more here.

🧩 Key Takeaways

• ✅ This is a minimum spanning tree problem, which means connect everything for the least total cost.
• ✅ Prim’s algorithm grows the tree one point at a time, always taking the cheapest reaching wire.
• ✅ The cost between two points is their Manhattan distance, the sum of the x gap and the y gap.
• ✅ After adding a point, update the costs of the remaining outside points.
• ✅ The dense array version runs in O(n²) time, which fits a fully connected graph.

🚀 What’s Next?

• Network Delay Time
• Cheapest Flights Within K Stops