1584. Min Cost to Connect All Points (Medium)

Problem

Given n points on a 2D plane, connect them all with the minimum total cost, where the cost between two points is their Manhattan distance (|x1 - x2| + |y1 - y2|). Return the minimum total cost.

Example

points = [[0,0],[2,2],[3,10],[5,2],[7,0]] → 20
points = [[3,12],[-2,5],[-4,1]] → 18

LeetCode 1584 · Link · Medium

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, try all spanning trees

Generate every (n-1)-subset of edges; check if each forms a spanning tree (acyclic and connects all nodes). Track the minimum total weight.

from itertools import combinations

def min_cost_connect_points(points):
    n = len(points)
    if n <= 1:
        return 0
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
            edges.append((d, i, j))

    best = float('inf')
    for combo in combinations(edges, n - 1):              # L1: C(E, n-1) subsets
        parent = list(range(n))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        total = 0
        ok = True
        for d, i, j in combo:                              # L2: check acyclic via Union-Find
            ri, rj = find(i), find(j)
            if ri == rj:
                ok = False
                break
            parent[ri] = rj
            total += d
        if ok:                                             # connected if no cycle and exactly n-1 edges
            best = min(best, total)
    return best

function minCostConnectPoints(points: number[][]): number {
    const n = points.length;
    if (n <= 1) return 0;
    const edges: [number, number, number][] = [];
    for (let i = 0; i < n; i++)
        for (let j = i + 1; j < n; j++) {
            const d = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
            edges.push([d, i, j]);
        }

    // generate all (n-1)-subsets; exponential -- only works for tiny n
    let best = Infinity;
    function choose(start: number, combo: [number, number, number][]): void {
        if (combo.length === n - 1) {                      // L1: check each subset
            const parent = Array.from({ length: n }, (_, i) => i);
            function find(x: number): number {
                while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
                return x;
            }
            let total = 0, ok = true;
            for (const [d, i, j] of combo) {              // L2: check acyclic via Union-Find
                const ri = find(i), rj = find(j);
                if (ri === rj) { ok = false; break; }
                parent[ri] = rj; total += d;
            }
            if (ok) best = Math.min(best, total);
            return;
        }
        for (let k = start; k < edges.length; k++) {
            combo.push(edges[k]);
            choose(k + 1, combo);
            combo.pop();
        }
    }
    choose(0, []);
    return best;
}

// Brute force: enumerate all (n-1)-subsets of edges. Exponential -- skip for n > 8.
// See 1584-min-cost-to-connect-all-points.go for the stub to implement.

final class Solution {
    func minCostConnectPoints(_ points: [[Int]]) -> Int {
        let n = points.count; if n <= 1 { return 0 }
        var edges: [(Int, Int, Int)] = []
        for i in 0..<n { for j in (i + 1)..<n { edges.append((i, j, abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]))) } }
        var selected: [Int] = [], answer = Int.max
        func evaluate() {
            var parent = Array(0..<n)
            func find(_ value: Int) -> Int { var node = value; while parent[node] != node { node = parent[node] }; return node }
            var total = 0
            for index in selected { let edge = edges[index], a = find(edge.0), b = find(edge.1); if a == b { return }; parent[b] = a; total += edge.2 }
            answer = min(answer, total)
        }
        func choose(_ index: Int) { if selected.count == n - 1 { evaluate(); return }; if index == edges.count || selected.count + edges.count - index < n - 1 { return }; selected.append(index); choose(index + 1); selected.removeLast(); choose(index + 1) }
        choose(0); return answer
    }
}

By Cayley’s formula, K_n has n^(n-2) spanning trees, so this explodes past n ≈ 8.

Complexity

Time: exponential in edges.
Space: exponential.

Skip.

Approach 2: Kruskal’s algorithm (sort edges + union-find)

Compute all n(n-1)/2 pairwise distances; sort by weight; add edges in order if they don’t create a cycle.

def min_cost_connect_points(points):
    n = len(points)                                                   # L1: O(1)
    edges = []                                                        # L2: O(1)
    for i in range(n):                                                # L3: outer loop, n iterations
        for j in range(i + 1, n):                                     # L4: inner loop, n-i-1 iterations
            d = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])  # L5: O(1) per pair
            edges.append((d, i, j))                                   # L6: O(1) amortized
    edges.sort()                                                      # L7: O(E log E) where E = n(n-1)/2

    parent = list(range(n))                                           # L8: O(n)
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]                            # L9: path compression, amortized O(alpha(n))
            x = parent[x]
        return x

    total = 0
    edges_added = 0
    for d, i, j in edges:                                             # L10: iterate over sorted edges, up to E iterations
        ri, rj = find(i), find(j)                                     # L11: O(alpha(n)) per find
        if ri != rj:
            parent[ri] = rj                                           # L12: O(1) union
            total += d                                                # L13: O(1)
            edges_added += 1
            if edges_added == n - 1:                                  # L14: early exit once MST complete
                break
    return total

function minCostConnectPoints(points: number[][]): number {
    const n = points.length;                                                   // L1: O(1)
    const edges: [number, number, number][] = [];                              // L2: O(1)
    for (let i = 0; i < n; i++)                                                // L3: outer loop, n iterations
        for (let j = i + 1; j < n; j++) {                                     // L4: inner loop, n-i-1 iterations
            const d = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);  // L5: O(1)
            edges.push([d, i, j]);                                             // L6: O(1) amortized
        }
    edges.sort((a, b) => a[0] - b[0]);                                        // L7: O(E log E)

    const parent = Array.from({ length: n }, (_, i) => i);                    // L8: O(n)
    function find(x: number): number {
        while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }  // L9: path compression
        return x;
    }

    let total = 0, added = 0;
    for (const [d, i, j] of edges) {                                           // L10: iterate sorted edges
        const ri = find(i), rj = find(j);                                      // L11: O(alpha(n)) per find
        if (ri !== rj) {
            parent[ri] = rj;                                                   // L12: O(1) union
            total += d;                                                        // L13: O(1)
            if (++added === n - 1) break;                                      // L14: early exit once MST complete
        }
    }
    return total;
}

// See 1584-min-cost-to-connect-all-points-approach2.go for the full runnable program.
func minCostConnectPoints(points [][]int) int {
    n := len(points)                                                           // L1: O(1)
    type Edge struct{ d, i, j int }
    var edges []Edge                                                           // L2: O(1)
    for i := 0; i < n; i++ {                                                  // L3: outer loop
        for j := i + 1; j < n; j++ {                                         // L4: inner loop
            d := abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1])  // L5: O(1)
            edges = append(edges, Edge{d, i, j})                              // L6: O(1) amortized
        }
    }
    sort.Slice(edges, func(a, b int) bool { return edges[a].d < edges[b].d }) // L7: O(E log E)
    parent := make([]int, n)                                                   // L8: O(n)
    for i := range parent { parent[i] = i }
    var find func(int) int
    find = func(x int) int {
        for parent[x] != x { parent[x] = parent[parent[x]]; x = parent[x] }  // L9: path compression
        return x
    }
    total, added := 0, 0
    for _, e := range edges {                                                  // L10: iterate sorted edges
        ri, rj := find(e.i), find(e.j)                                        // L11: O(alpha(n)) per find
        if ri != rj {
            parent[ri] = rj                                                    // L12: O(1) union
            total += e.d                                                       // L13: O(1)
            added++
            if added == n-1 { break }                                         // L14: early exit
        }
    }
    return total
}

Where the time goes, line by line

Variables: V = len(points), E = V² (complete graph of pairwise distances).

Line	Per-call cost	Times executed	Contribution
L3/L4 (edge generation)	$O(1)$	E = V(V-1)/2	$O(V²)$
L5/L6 (compute + append)	$O(1)$	E	$O(V²)$
L7 (sort edges)	$O(E log E)$	1	$O(V² log V)$ ← dominates
L8 (init parent)	$O(V)$	1	$O(V)$
L10/L11 (UF loop)	$O(alpha(V)$ )	up to E	$O(V²)$ effectively
L12/L13 (union + sum)	$O(1)$	V-1	$O(V)$

Sorting E = $O(V²)$ edges costs $O(V² log V² )$ = $O(V² log V)$ . The union-find loop is fast (nearly linear via path compression and union by rank), but it runs over V² edges in the worst case; however, it exits as soon as V-1 edges are added, so it often terminates well before that.

Complexity

Time: $O(V² log V)$ , driven by L7 (sorting all pairwise edges).
Space: $O(V²)$ for the edge list.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func minCostConnectPoints(_ points: [[Int]]) -> Int {
        let n = points.count; if n <= 1 { return 0 }; var edges: [(Int, Int, Int)] = []
        for i in 0..<n { for j in (i + 1)..<n { edges.append((abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j)) } }; edges.sort { $0.0 < $1.0 }
        var parent = Array(0..<n), rank = Array(repeating: 0, count: n)
        func find(_ value: Int) -> Int { var node = value; while parent[node] != node { node = parent[node] }; return node }
        var total = 0, used = 0
        for edge in edges { var a = find(edge.1), b = find(edge.2); if a == b { continue }; if rank[a] < rank[b] { swap(&a, &b) }; parent[b] = a; if rank[a] == rank[b] { rank[a] += 1 }; total += edge.0; used += 1; if used == n - 1 { break } }
        return total
    }
}

Approach 3: Prim’s algorithm with a priority queue (optimal for dense graphs)

Grow the MST one node at a time; maintain a priority queue of (distance, node) pairs for candidate extensions.

import heapq

def min_cost_connect_points(points):
    n = len(points)                                                   # L1: O(1)
    visited = [False] * n                                             # L2: O(n)
    heap = [(0, 0)]                                                   # L3: O(1), seed with node 0 at cost 0
    total = 0
    count = 0

    while heap and count < n:                                         # L4: loop runs until all nodes added
        d, u = heapq.heappop(heap)                                    # L5: O(log(heap size)) per pop
        if visited[u]:                                                # L6: skip stale entries
            continue
        visited[u] = True                                             # L7: O(1)
        total += d                                                    # L8: O(1)
        count += 1
        for v in range(n):                                            # L9: scan all nodes for neighbors
            if not visited[v]:
                dist = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])  # L10: O(1)
                heapq.heappush(heap, (dist, v))                       # L11: O(log(heap size)) per push

    return total

function minCostConnectPoints(points: number[][]): number {
    const n = points.length;                                                   // L1: O(1)
    const visited = new Array(n).fill(false);                                  // L2: O(n)
    const heap = new MinHeap();
    heap.push([0, 0]);                                                         // L3: O(1), seed with node 0 at cost 0
    let total = 0, count = 0;

    while (heap.size > 0 && count < n) {                                       // L4: loop runs until all nodes added
        const [d, u] = heap.pop();                                             // L5: O(log(heap size)) per pop
        if (visited[u]) continue;                                              // L6: skip stale entries
        visited[u] = true;                                                     // L7: O(1)
        total += d;                                                            // L8: O(1)
        count++;
        for (let v = 0; v < n; v++) {                                          // L9: scan all nodes for neighbors
            if (!visited[v]) {
                const dist = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);  // L10: O(1)
                heap.push([dist, v]);                                          // L11: O(log(heap size)) per push
            }
        }
    }
    return total;
}

// See 1584-min-cost-to-connect-all-points-approach3.go for the full runnable program.
func minCostConnectPoints(points [][]int) int {
    n := len(points)                                                   // L1: O(1)
    visited := make([]bool, n)                                         // L2: O(n)
    h := &MinHeap1584{{d: 0, u: 0}}
    heap.Init(h)                                                       // L3: O(1), seed with node 0 at cost 0
    total, count := 0, 0
    for h.Len() > 0 && count < n {                                     // L4: loop runs until all nodes added
        item := heap.Pop(h).(Item1584)
        d, u := item.d, item.u                                         // L5: O(log(heap size)) per pop
        if visited[u] { continue }                                     // L6: skip stale entries
        visited[u] = true                                              // L7: O(1)
        total += d                                                     // L8: O(1)
        count++
        for v := 0; v < n; v++ {                                       // L9: scan all nodes for neighbors
            if !visited[v] {
                dist := abs(points[u][0]-points[v][0]) + abs(points[u][1]-points[v][1])  // L10: O(1)
                heap.Push(h, Item1584{d: dist, u: v})                  // L11: O(log(heap size)) per push
            }
        }
    }
    return total
}

Where the time goes, line by line

Variables: V = len(points), E = V² (complete graph of pairwise distances).

Line	Per-call cost	Times executed	Contribution
L2 (init visited)	$O(V)$	1	$O(V)$
L4 (loop)	$O(1)$	up to E	$O(E)$ = $O(V²)$
L5 (heappop)	$O(log E)$	up to E	$O(E log E)$ = $O(V² log V)$ ← dominates
L9/L10 (neighbor scan)	$O(1)$	V per accepted node	$O(V²)$ total
L11 (heappush)	$O(log E)$	up to E	$O(V² log V)$ ← ties

Each accepted node triggers V neighbor pushes, and each push/pop costs $O(log E)$ = $O(log V² )$ = $O(2 log V)$ = $O(log V)$ . With V nodes accepted and V neighbors each, we get $O(V² log V)$ total.

Complexity

Time: $O(V² log V)$ , driven by L5/L11 (heap operations over E candidate edges).
Space: $O(V²)$ heap worst case (all edges can be in the heap simultaneously).

For dense graphs (complete graphs like this one), a simpler $O(V²)$ Prim’s variant (without a heap, using an array of “cheapest to add”) matches the lower bound.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Array-based Prim’s (best for dense graphs)

def min_cost_connect_points(points):
    n = len(points)                                                   # L1: O(1)
    in_mst = [False] * n                                              # L2: O(n)
    min_dist = [float('inf')] * n                                     # L3: O(n)
    min_dist[0] = 0
    total = 0
    for _ in range(n):                                                # L4: outer loop, n iterations
        # pick the unvisited node with smallest min_dist
        u = -1
        for v in range(n):                                            # L5: linear scan, O(n) per outer iteration
            if not in_mst[v] and (u == -1 or min_dist[v] < min_dist[u]):
                u = v
        in_mst[u] = True                                              # L6: O(1)
        total += min_dist[u]                                          # L7: O(1)
        for v in range(n):                                            # L8: update min_dist for all neighbors
            if not in_mst[v]:
                d = abs(points[u][0] - points[v][0]) + abs(points[u][1] - points[v][1])  # L9: O(1)
                if d < min_dist[v]:
                    min_dist[v] = d                                   # L10: O(1)
    return total

function minCostConnectPoints(points: number[][]): number {
    const n = points.length;                                                   // L1: O(1)
    const inMst = new Array(n).fill(false);                                    // L2: O(n)
    const minDist = new Array(n).fill(Infinity);                               // L3: O(n)
    minDist[0] = 0;
    let total = 0;

    for (let iter = 0; iter < n; iter++) {                                     // L4: outer loop, n iterations
        let u = -1;
        for (let v = 0; v < n; v++) {                                          // L5: linear scan, O(n) per outer iteration
            if (!inMst[v] && (u === -1 || minDist[v] < minDist[u])) u = v;
        }
        inMst[u] = true;                                                       // L6: O(1)
        total += minDist[u];                                                   // L7: O(1)
        for (let v = 0; v < n; v++) {                                          // L8: update minDist for all neighbors
            if (!inMst[v]) {
                const d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);  // L9: O(1)
                if (d < minDist[v]) minDist[v] = d;                           // L10: O(1)
            }
        }
    }
    return total;
}

// See 1584-min-cost-to-connect-all-points-approach4.go for the full runnable program.
func minCostConnectPoints(points [][]int) int {
    n := len(points)                                                   // L1: O(1)
    inMst := make([]bool, n)                                           // L2: O(n)
    minDist := make([]int, n)                                          // L3: O(n)
    for i := range minDist { minDist[i] = 1<<31 - 1 }
    minDist[0] = 0
    total := 0
    for range points {                                                 // L4: outer loop, n iterations
        u := -1
        for v := 0; v < n; v++ {                                       // L5: linear scan, O(n)
            if !inMst[v] && (u == -1 || minDist[v] < minDist[u]) { u = v }
        }
        inMst[u] = true                                                // L6: O(1)
        total += minDist[u]                                            // L7: O(1)
        for v := 0; v < n; v++ {                                       // L8: update minDist
            if !inMst[v] {
                d := abs(points[u][0]-points[v][0]) + abs(points[u][1]-points[v][1])  // L9: O(1)
                if d < minDist[v] { minDist[v] = d }                  // L10: O(1)
            }
        }
    }
    return total
}

Where the time goes, line by line

Variables: V = len(points), E = V² (complete graph of pairwise distances).

Line	Per-call cost	Times executed	Contribution
L2/L3 (init arrays)	$O(V)$	1	$O(V)$
L4 (outer loop)	$O(1)$	V	$O(V)$
L5 (linear min scan)	$O(V)$	V	$O(V²)$ ← dominates
L6/L7 (mark + sum)	$O(1)$	V	$O(V)$
L8/L9/L10 (dist update)	$O(V)$	V	$O(V²)$ ← ties

No heap needed. The inner scans at L5 and L8 each visit all V nodes once per outer iteration, giving exactly V² operations. This is optimal for dense graphs: you can’t do better than $O(V²)$ when there are V² edges to consider.

Complexity

Time: $O(V²)$ , driven by L5/L8 (the two inner loops over all V nodes).
Space: $O(V)$ for in_mst and min_dist.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

final class Solution {
    func minCostConnectPoints(_ points: [[Int]]) -> Int {
        let n = points.count; if n <= 1 { return 0 }; var visited = Array(repeating: false, count: n), total = 0, used = 0
        var queue = BinaryHeap<(Int, Int)>(hasHigherPriority: { $0.0 < $1.0 }); queue.insert((0, 0))
        while used < n, let (cost, node) = queue.removeRoot() { if visited[node] { continue }; visited[node] = true; total += cost; used += 1; for next in 0..<n where !visited[next] { let distance = abs(points[node][0] - points[next][0]) + abs(points[node][1] - points[next][1]); queue.insert((distance, next)) } }
        return total
    }
}

Summary

Approach	Time	Space
Enumerate spanning trees	exponential	exponential
Kruskal’s (sort + UF)	$O(V² log V)$	$O(V²)$
Prim’s with heap	$O(V² log V)$	$O(V²)$
Prim’s array-based (dense)	$O(V²)$	$O(V)$

For dense graphs (as here), array-based Prim’s is optimal. For sparse graphs, heap-based Prim’s or Kruskal’s is better.

Test cases

# Quick smoke tests, paste into a REPL or save as test_1584.py and run.
# Uses the canonical implementation (array-based Prim's, optimal for dense graphs).

def min_cost_connect_points(points):
    n = len(points)
    in_mst = [False] * n
    min_dist = [float('inf')] * n
    min_dist[0] = 0
    total = 0
    for _ in range(n):
        u = -1
        for v in range(n):
            if not in_mst[v] and (u == -1 or min_dist[v] < min_dist[u]):
                u = v
        in_mst[u] = True
        total += min_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 < min_dist[v]:
                    min_dist[v] = d
    return total

def _run_tests():
    # Example 1 from problem statement
    assert min_cost_connect_points([[0,0],[2,2],[3,10],[5,2],[7,0]]) == 20
    # Example 2 from problem statement
    assert min_cost_connect_points([[3,12],[-2,5],[-4,1]]) == 18
    # Single point: no edges needed
    assert min_cost_connect_points([[0,0]]) == 0
    # Two points: single edge
    assert min_cost_connect_points([[0,0],[1,1]]) == 2
    # All points on same horizontal line
    assert min_cost_connect_points([[0,0],[1,0],[2,0],[3,0]]) == 3
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

function minCostConnectPoints(points: number[][]): number {
    const n = points.length;
    const inMst = new Array(n).fill(false);
    const minDist = new Array(n).fill(Infinity);
    minDist[0] = 0;
    let total = 0;
    for (let iter = 0; iter < n; iter++) {
        let u = -1;
        for (let v = 0; v < n; v++) {
            if (!inMst[v] && (u === -1 || minDist[v] < minDist[u])) u = v;
        }
        inMst[u] = true;
        total += minDist[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 < minDist[v]) minDist[v] = d;
            }
        }
    }
    return total;
}

console.assert(minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]]) === 20);
console.assert(minCostConnectPoints([[3,12],[-2,5],[-4,1]]) === 18);
console.assert(minCostConnectPoints([[0,0]]) === 0);
console.assert(minCostConnectPoints([[0,0],[1,1]]) === 2);
console.assert(minCostConnectPoints([[0,0],[1,0],[2,0],[3,0]]) === 3);
console.log("all tests pass");

Graphs, MST via Prim’s / Kruskal’s
Heaps / Priority Queues, Prim’s edge selection

Union Find, the component tracking structure for connectivity as edges are processed.
Greedy Algorithms, the local choice pattern protected by an invariant about the best reachable future.

1584. Min Cost to Connect All Points (Medium)

Problem

Try it yourself

Approach 1: Brute force, try all spanning trees

Approach 2: Kruskal’s algorithm (sort edges + union-find)

Approach 3: Prim’s algorithm with a priority queue (optimal for dense graphs)

Array-based Prim’s (best for dense graphs)

Summary

Test cases

Related data structures

Related concepts