Min Cost to Connect Points

Problem Statement

You are given a 2-D integer array points, where points[i] = [xi, yi]. Each points[i] represents a distinct point on a 2-D plane.

The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between the two points, i.e. $|xi - xj| + |yi - yj|$.

Return the minimum cost to connect all points together, such that there exists exactly one path between each pair of points.

Example 1:

Input: points = [[0,0],[2,2],[3,3],[2,4],[4,2]]

Output: 10

Constraints:

• 1 <= points.length <= 1000
• -1000 <= xi, yi <= 1000

You should aim for a solution as good or better than O(n^2 \log n) time and O(n^2) space, where n is the number of points.

Recommended Time and Space Complexity

You should aim for a solution as good or better than O(n^2 \log n) time and O(n^2) space, where n is the number of points.

Hint 1

Think of this problem as a graph, where the given points represent nodes. We need to connect these nodes into a single component by creating edges. Can you think of an advanced graph algorithm that can be used to connect all points into one component?

Hint 2

We use Kruskal’s algorithm along with Union-Find (DSU) to connect nodes into components. The final component forms the minimum spanning tree (MST), where the edges between nodes are weighted by the Manhattan distance, and the total weight of the tree is minimized. How would you implement this?

Hint 3

We create the possible edges by iterating through every pair of points and calculating the weights as the Manhattan distance between them. Next, we sort the edges in ascending order based on their weights, as we aim to minimize the cost. Then, we traverse through these edges, connecting the nodes and adding the weight of the edge to the total cost if the edge is successfully added. The final result will be the minimum cost.

Solution

Kruskal’s Algorithm

class DSU:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, node):
        if self.parent[node] != node:
            self.parent[node] = self.find(self.parent[node])
        return self.parent[node]

    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu == pv:
            return False
        if self.size[pu] < self.size[pv]:
            pu, pv = pv, pu
        self.size[pu] += self.size[pv]
        self.parent[pv] = pu
        return True


def min_cost_connect_points(points: list[list[int]]) -> int:
    n = len(points)
    dsu = DSU(n)
    edges = []
    for i in range(n):
        x1, y1 = points[i]
        for j in range(i + 1, n):
            x2, y2 = points[j]
            dist = abs(x1 - x2) + abs(y1 - y2)
            edges.append((dist, i, j))

    edges.sort()
    result = 0
    for dist, u, v in edges:
        if dsu.union(u, v):
            result += dist
    return result

Time complexity: O(n^2 \log n) Space complexity: O(n^2)