Domain 2MediumMEDIUM

Min Cost to Connect All Points

Solve the Minimum Spanning Tree problem on a complete graph using Kruskal's Algorithm with Union-Find to ensure connectivity at minimum Manhattan distance cost.

Domain: medium•Updated: 2026-09-18
#MST#Union-Find (DSU)#$O(N^2 log N)$#$O(N^2)

Problem Breakdown

We are given N points in a 2D plane and need to connect them such that all points form a single connected component (a tree structure) with the minimum total edge weight. The connectivity requirement (“exactly one simple path between any two points”) confirms we must find a Minimum Spanning Tree (MST).

The graph is “complete” because every point can be connected to every other point, but calculating all edges explicitly (N2N^2) creates a dense graph scenario.

  • Input: List of coordinate pairs points.
  • Output: Integer representing the minimum total cost.
  • Edge Weights: Manhattan distance ∣xi−xj∣+∣yi−yj∣|x_i - x_j| + |y_i - y_j|.

Intuition

This is a classic MST problem on a complete graph where edge weights are defined by geometry (Manhattan distance). To find the MST, we need to select edges that connect components without forming cycles while minimizing total weight.

Two primary algorithms exist:

  1. Kruskal’s Algorithm: Sorts all edges and adds them greedily if they don’t form a cycle using Union-Find. Complexity is dominated by sorting EE edges (O(Elog⁡E)O(E \log E)). Since it’s a complete graph, E=N(N−1)/2E = N(N-1)/2, leading to roughly O(N2log⁡N)O(N^2 \log N).
  2. Prim’s Algorithm: Grows the tree from an existing node using Dijkstra-like logic or a priority queue. For dense graphs (like this one), Prim’s with an array-based implementation runs in O(V2)O(V^2), which is theoretically faster (N=1000N=1000 vs sorting).

However, since Union-Find tags are often associated with MST problems on LeetCode and Kruskal’s logic is intuitive for “picking cheapest edges,” we will implement Kruskal’s Algorithm. We must ensure the implementation handles Python recursion limits (default 1000) by using an iterative find operation or union-by-rank, as a degenerate tree could hit stack depth limits.

Approach

We use Kruskal’s Algorithm combined with Union-Find:

  1. Edge Generation: Iterate through all unique pairs of points (i,j)(i, j) where j>ij > i. Calculate the Manhattan distance and store (cost, u, v). This takes O(N2)O(N^2) time/space.
  2. Sorting: Sort the edge list by cost in ascending order (O(Elog⁡E)O(E \log E)).
  3. Union-Find Initialization: Initialize a Disjoint Set Union (DSU) structure where each point is its own parent set.
  4. Greedy Selection: Iterate through sorted edges:
    • Use find to get root parents of both points in the edge.
    • If roots differ, perform union, add cost to total, and increment connected components count (or decrement component sets).
  5. Termination: Stop when we have selected N−1N-1 edges or run out of edges.

Complexity Analysis

  • Time Complexity:
    • Generating all pairs: O(N2)O(N^2).
    • Sorting edges (E≈N2/2E \approx N^2/2): O(Elog⁡E)=O((N2)⋅2log⁡(N))=O(N2log⁡N)O(E \log E) = O((N^2) \cdot 2\log(N)) = O(N^2 \log N).
    • Union-Find operations: Amortized nearly constant time per operation. Total is dominated by sorting.
    • Overall: O(N2log⁡N)O(N^2 \log N). For N=1000N=1000, this fits within standard limits (approx 5 million ops). Note that Prim’s algorithm could achieve O(N2)O(N^2), but Kruskal’s passes comfortably here and demonstrates DSU mastery.
  • Space Complexity:
    • Storing the edge list requires storing ≈N2/2\approx N^2/2 tuples. This results in O(N2)O(N^2) space (roughly 500k entries for N=1000N=1000, well within memory limits).

Solution

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    # Iterative find to prevent RecursionError on deep trees (depth up to N)
    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        
        # Path compression
        curr = x
        while curr != root:
            next_node = self.parent[curr]
            self.parent[curr] = root
            curr = next_node
        
        return root
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        
        if rootX == rootY:
            return False
        
        # Union by rank/size is omitted for brevity but simple linking works. 
        # We link one to the other arbitrarily here.
        self.parent[rootX] = rootY
        return True

class Solution:
    def minCost(self, points):
        n = len(points)
        
        # Edge case: 0 or 1 point requires no cost to connect
        if n <= 1:
            return 0
        
        edges = []
        
        # Generate all possible edges with Manhattan distance weights
        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                cost = abs(x1 - x2) + abs(y1 - y2)
                edges.append((cost, i, j))
        
        # Sort edges by weight (Kruskal's greedy step)
        edges.sort()
        
        uf = UnionFind(n)
        total_cost = 0
        
        for cost, u, v in edges:
            if uf.union(u, v):
                total_cost += cost
                
                # Optimization check is implicit; we can stop early 
                # but iterating the sorted list until exhaustion is fast enough.

        return total_cost

Edge Cases Handled

  • Single Point (N=1): The code checks if n <= 1 immediately returning 0, preventing empty edge generation loops or index errors.
  • Negative Coordinates: Manhattan distance uses absolute values, so negative inputs are handled correctly without special logic (e.g., -5 - (-3) = -2, abs is 2).
  • Large Coordinate Values: Python handles large integers automatically; no overflow checks needed for the cost calculation itself.
  • Recursion Limit Safety: The find method in Union-Find uses an iterative approach instead of recursion to avoid hitting Python’s default stack depth limit (1000) when N=1000N=1000.