Min Cost to Connect All Points

35 min · minCostConnectPoints()

You need to wire every field sensor together, and every extra metre of cable costs money.

Each entry [x, y] in points is a distinct point on a 2D grid. Connecting [x1, y1] and [x2, y2] costs their Manhattan distance — the grid-walking distance |x1 - x2| + |y1 - y2|.

Return the smallest total cost that makes all points part of one connected structure. You may connect any pair, directly or through other points. The chosen connections form a minimum spanning tree (MST): a cheapest set of edges that connects every point without needing a cycle.

Constraints

1 <= points.length <= 1_000
Every points[i] is [x, y] with -1_000_000 <= x, y <= 1_000_000.
All points are distinct.
The minimum total cost is less than 2^31.

Hints

See the hidden graph

Treat every point as a node and every pair as a possible weighted edge. You need an MST, but building all n(n - 1) / 2 edges costs quadratic memory.

Grow one connected region

Prim's algorithm starts from any point. Repeatedly add the outside point with the cheapest connection to the region already built.

Generate distances only when needed

Store, for each unchosen point, its cheapest distance to any chosen point. After adding one point, scan all unchosen points and update those values directly.

Follow-up

For millions of points, even O(n²) distance checks are too many. What geometric structure might help you avoid considering every possible pair?

Visible cases

Examples

Example 1

ready

Input: points = [ [ 0, 0 ], [ 2, 2 ], [ 3, 10 ], [ 5, 2 ], [ 7, 0 ] ]
Expected: 20
Why: the cheapest spanning connections have total Manhattan cost 20

Example 2

ready

Input: points = [ [ 3, 12 ], [ -2, 5 ], [ -4, 1 ] ]
Expected: 18
Why: connecting through [-2, 5] costs 12 + 6

Example 3

ready

Input: points = [ [ 4, -7 ] ]
Expected: 0
Why: one point is already connected

Interview signal

Asked at

AmazonGoogle

Kruskal's algorithm — sort every possible connection

Kruskal's algorithm is a direct MST choice: sort edges from cheapest to most expensive, then accept an edge when it joins two components that weren't connected before. A union-find is a structure that tracks those components and merges them efficiently.

The catch is the graph. Every pair of points is an edge, so Kruskal must first build and sort about n² / 2 connections.

def min_cost_connect_points(points: list[list[int]]) -> int:
    n = len(points)
    edges: list[tuple[int, int, int]] = []
    for first in range(n):
        for second in range(first + 1, n):
            distance = (
                abs(points[first][0] - points[second][0])
                + abs(points[first][1] - points[second][1])
            )
            edges.append((distance, first, second))
    edges.sort()
 
    parent = list(range(n))
    size = [1] * n
 
    def find(point: int) -> int:
        while point != parent[point]:
            parent[point] = parent[parent[point]]
            point = parent[point]
        return point
 
    total = used = 0
    for distance, first, second in edges:
        root_a, root_b = find(first), find(second)
        if root_a == root_b:
            continue
        if size[root_a] < size[root_b]:
            root_a, root_b = root_b, root_a
        parent[root_b] = root_a
        size[root_a] += size[root_b]
        total += distance
        used += 1
        if used == n - 1:
            break
    return total

Time O(n² log n) to sort O(n²) edges. Space O(n²) for the complete edge list.

Dense Prim's algorithm — grow the tree without storing edges

Prim's algorithm is the right choice because the Manhattan graph is complete and dense. An O(n²) version calculates an edge only when it needs that distance, avoiding the quadratic edge list and its sort.

Maintain best[i], the cheapest connection from point i to the tree built so far. Each round selects the unused point with the smallest best value, pays that cost, and uses the new point to improve every remaining value.

def min_cost_connect_points(points: list[list[int]]) -> int:
    n = len(points)
    in_tree = [False] * n
    best = [float("inf")] * n
    best[0] = 0
    total = 0
 
    for _ in range(n):
        next_point = -1
        for point in range(n):
            if not in_tree[point] and (
                next_point == -1 or best[point] < best[next_point]
            ):
                next_point = point
 
        in_tree[next_point] = True
        total += int(best[next_point])
        for point in range(n):
            if in_tree[point]:
                continue
            distance = (
                abs(points[next_point][0] - points[point][0])
                + abs(points[next_point][1] - points[point][1])
            )
            if distance < best[point]:
                best[point] = distance
 
    return total

No heap is needed. Finding the next point already takes an O(n) scan, and updating its connections takes another O(n) scan. On this dense implicit graph, that clean quadratic loop is exactly the trade you want.

Time O(n²) for n selection-and-update rounds. Space O(n) for the membership and best-connection arrays.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arraypoints: int[][]

Expected

Run: visible + custom · Submit: full suite