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 () creates a dense graph scenario.
- Input: List of coordinate pairs
points. - Output: Integer representing the minimum total cost.
- Edge Weights: Manhattan distance .
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:
- 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 edges (). Since it’s a complete graph, , leading to roughly .
- 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 , which is theoretically faster ( 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:
- Edge Generation: Iterate through all unique pairs of points where . Calculate the Manhattan distance and store
(cost, u, v). This takes time/space. - Sorting: Sort the edge list by cost in ascending order ().
- Union-Find Initialization: Initialize a Disjoint Set Union (DSU) structure where each point is its own parent set.
- Greedy Selection: Iterate through sorted edges:
- Use
findto 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).
- Use
- Termination: Stop when we have selected edges or run out of edges.
Complexity Analysis
- Time Complexity:
- Generating all pairs: .
- Sorting edges (): .
- Union-Find operations: Amortized nearly constant time per operation. Total is dominated by sorting.
- Overall: . For , this fits within standard limits (approx 5 million ops). Note that Prim’s algorithm could achieve , but Kruskal’s passes comfortably here and demonstrates DSU mastery.
- Space Complexity:
- Storing the edge list requires storing tuples. This results in space (roughly 500k entries for , 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 checksif n <= 1immediately returning0, 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
findmethod in Union-Find uses an iterative approach instead of recursion to avoid hitting Python’s default stack depth limit (1000) when .