Min Cost to Connect All Points

MEDIUM✓ CHIP-TIMEDLC #1584 — FULL STATEMENT ↗

The drill: Wire every point on the plane into one network, where the cost of a wire is the Manhattan distance between its two ends. Spend the least total wire that still leaves everything connected.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A set of points on a 2D plane arrives, and any two of them can be joined by a direct wire. The cost of a wire between two points is their Manhattan distance — the sum of the horizontal and vertical gaps between them.

The goal is to choose a set of wires that leaves every point reachable from every other point, using the least total wire cost possible. Extra wires that don't help connectivity are pure waste.

There's no requirement on which specific wires get chosen — only that the whole set of points ends up in one connected network for the smallest total spend.

EX 01

points = [[0, 0]]

→ 0

SINGLE POINT, NOTHING TO CONNECT

EX 02

points = [[0, 0], [3, 4]]

→ 7

TWO POINTS, ONE EDGE

EX 03

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

→ 20

SELF-AUTHORED 5-POINT SPREAD

point count can run into the low thousands
coordinates are integers, can be negative
cost between any two points is their Manhattan distance
output is a single total cost, not the list of chosen wires

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Any set of wires that connects everyone without a single redundant loop is a spanning tree. There are exponentially many of them — the question is only which one is cheapest.

HINT 2 THE STRUCTURE

Grow the network one point at a time: always attach whichever outside point is currently closest to the network you've already built. That greedy rule provably never needs to undo a choice.

HINT 3 ONE STEP FROM THE ANSWER

Track, for every point not yet in the tree, its current cheapest distance to the tree. Each round, pull in the smallest of those, then update the rest against the newly added point — n rounds, n candidates scanned each round.

COACH'S BOARD — THE PATTERN, STEP BY STEP

WIRING THE CHEAPEST NETPATTERN · PRIM'S, ARRAY NOT HEAPpoints: (0,0) (2,2) (3,10) (5,2) (7,0)

STEP 1

5 points, Prim's MST: start the tree at point 0 and repeatedly pull in whichever unconnected point is cheapest to reach — a plain array scan, no heap needed.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/min-cost-to-connect-all-points.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 1:
            return 0
        in_mst = [False] * n
        min_dist = [float('inf')] * n
        min_dist[0] = 0
        total = 0
        for _ in range(n):
            u = -1
            best = float('inf')
            for i in range(n):
                if not in_mst[i] and min_dist[i] < best:
                    best = min_dist[i]
                    u = i
            in_mst[u] = True
            total += best
            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 < min_dist[v]:
                        min_dist[v] = d
        return total

TIME O(V²)SPACE O(V)PYTHON · RACE PACE · 24 LN

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 1:
            return 0
        edges = []
        for i in range(n):
            for j in range(i + 1, n):
                dist = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
                edges.append((dist, i, j))
        edges.sort()
        adj = collections.defaultdict(list)
        total = 0
        count = 0
        for dist, u, v in edges:
            if count == n - 1:
                break
            if not self._connected(adj, u, v):
                adj[u].append(v)
                adj[v].append(u)
                total += dist
                count += 1
        return total

    def _connected(self, adj, u, v):
        visited = {u}
        stack = [u]
        while stack:
            node = stack.pop()
            if node == v:
                return True
            for nb in adj[node]:
                if nb not in visited:
                    visited.add(nb)
                    stack.append(nb)
        return False

TIME O(V³)SPACE O(V²)PYTHON · TRAINING PACE · 36 LN

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

TIME O(V²)SPACE O(V)JAVA · RACE PACE · 29 LN

class Solution {
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        if (n <= 1) return 0;
        List<int[]> edges = new ArrayList<>(); // {dist, u, v}
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dist = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
                edges.add(new int[] { dist, i, j });
            }
        }
        edges.sort((a, b) -> a[0] - b[0]);
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int total = 0, count = 0;
        for (int[] e : edges) {
            if (count == n - 1) break;
            int u = e[1], v = e[2];
            if (!connected(adj, u, v)) {
                adj.get(u).add(v);
                adj.get(v).add(u);
                total += e[0];
                count++;
            }
        }
        return total;
    }

    private boolean connected(List<List<Integer>> adj, int u, int v) {
        Set<Integer> visited = new HashSet<>();
        visited.add(u);
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(u);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (node == v) return true;
            for (int nb : adj.get(node)) {
                if (!visited.contains(nb)) {
                    visited.add(nb);
                    stack.push(nb);
                }
            }
        }
        return false;
    }
}

TIME O(V³)SPACE O(V²)JAVA · TRAINING PACE · 46 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED