MediumArrayUnion FindGraphMinimum Spanning Tree

Min Cost to Connect All Points

1 approach, code in every language

You are given an array of distinct points on a 2D plane, where each point is written as [x, y]. The cost of connecting two points equals the Manhattan distance between them, that is |x1 - x2| + |y1 - y2|.

Every point must end up connected to every other point, directly or through intermediate points, and there must be exactly one simple path between any two points. Return the minimum total cost that achieves this.

Example 1

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

Output: 20

Connecting the points with the edges of total weight 20 links every point while keeping the sum of Manhattan distances as small as possible.

Example 2

Input: points = [[3,12],[-2,5],[-4,1]]

Output: 18

Constraints

1 <= points.length <= 1000
-10^6 <= xi, yi <= 10^6
All pairs (xi, yi) are distinct.

Kruskal with Union-Find

Enumerate every pair of points as a weighted edge, sort by Manhattan distance, then greedily add edges that merge separate components.

Loading animation…

Intuition

Connecting all points with the smallest total cost and exactly one path between any pair is precisely a Minimum Spanning Tree. Because any two points can be linked directly, the underlying graph is complete, so we can materialize all n*(n-1)/2 candidate edges. Kruskal's algorithm sorts these edges by weight and walks them from cheapest to most expensive. An edge is accepted only when its endpoints currently sit in different components, which a union-find structure checks in near-constant time. Once we have accepted n-1 edges, every point is joined and the accumulated weight is the answer.

Algorithm walkthrough

1Initialize a union-find over the n points, each point its own component.
2For every pair (i, j) build an edge whose weight is the Manhattan distance between points i and j.
3Sort all edges in non-decreasing order of weight.
4Scan the sorted edges; for each, find the roots of both endpoints.
5If the roots differ, union them, add the weight to the running total, and count the edge.
6Stop as soon as n-1 edges have been accepted and return the total cost.

Implementation

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        n = len(points)
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        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()
        total = 0
        used = 0
        for dist, i, j in edges:
            ri, rj = find(i), find(j)
            if ri != rj:
                parent[ri] = rj
                total += dist
                used += 1
                if used == n - 1:
                    break
        return total

Time

O(n^2 log n)

Space

O(n^2)

A complete graph has O(n^2) edges; sorting dominates. Union-find operations are near-constant with path compression.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Trenching the Sprinkler Valves is our own problem on the technique behind Min Cost to Connect All Points: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free