Problem overview
The function minCostConnectPoints(points) receives a list of n points, each an [x, y] pair. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|, the distance along grid lines. The function returns the least total cost that makes all the points connected, meaning you can get from any point to any other by following connections. There are up to 1000 points, with coordinates between -1,000,000 and 1,000,000, all distinct.
For [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]] the answer is 20: four connections costing 4, 3, 4 and 9. For [[3, 12], [-2, 5], [-4, 1]] it is 18, and for [[0, 0], [1, 0], [0, 1], [10, 10]] it is 21.
Approach: Kruskal's algorithm
Think of every pair of points as an edge of a graph, with the Manhattan distance as its cost. There are n · (n - 1) / 2 edges, which is 499,500 for 1000 points. Connecting all the points as cheaply as possible means choosing n - 1 edges that join everything with the least total cost: a minimum spanning tree. Any more edges would only close a cycle and add cost.
Kruskal's algorithm builds it greedily. Sort all the edges from cheapest to dearest, then go through them: take an edge if its two ends are in different groups, which joins the two groups into one, and skip it if both ends are already in the same group. After n - 1 edges taken, everything is one group and the work is done.
Taking the cheapest edge between two groups is always safe. The finished tree has to join those two groups somehow, and if it used a dearer edge there, swapping in the cheaper one gives a tree that costs no more.
To tell quickly whether two points are in the same group, the lesson uses union-find. Every point has a parent; a point that is its own parent is the root, and the root names the group. Two points are in one group exactly when they lead to the same root. Merging two groups hangs one root under the other.
The third example shows the skipping. The sorted edges, as (cost, i, j), are:
[(1, 0, 1), (1, 0, 2), (2, 1, 2), (19, 1, 3), (19, 2, 3), (20, 0, 3)]
Going through them:
(1, 0, 1) roots 0 1 take
(1, 0, 2) roots 0 2 take
(2, 1, 2) roots 0 0 skip
(19, 1, 3) roots 0 3 take
(19, 2, 3) roots 0 0 skip
(20, 0, 3) roots 0 0 skip
Points 1 and 2 are already joined through point 0, so the edge of cost 2 is skipped. The total is 1 + 1 + 19 = 21. (The function itself returns as soon as n - 1 edges are taken, so it stops after the edge (19, 1, 3).)
The cost is O(n² log n) time, from sorting the edges, and O(n²) space, for keeping them. Prim's algorithm is the other classic approach: it grows one tree from a starting point, always adding the cheapest edge to a new point, and on a graph where every pair is an edge it can run in O(n²) with a plain scan. This lesson uses Kruskal.
Step by step
- Store
n = len(points). Kruskal works on edges, so the next steps list every possible connection with its cost. - Create an empty list
edges. Each edge will be a tuple(cost, i, j). The cost comes first because the edges get sorted by it. - Loop
ioverrange(n). Together with the next loop, this visits every pair of points. - Loop
joverrange(i + 1, n)inside it. Starting ati + 1lists each pair once and never pairs a point with itself, since connectingitojcosts the same asjtoi. - Compute
cost. It isabs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]). The absolute value turns each difference into a distance, whichever point lies further left or lower. - Append
(cost, i, j)toedges. The inner parentheses make the tuple and the outer ones belong toappend. - Sort with
edges.sort(). Tuples compare by their first element first, so the edges end up ordered by cost. Ties are broken byiandj, which doesn't change the total. - Create
parent = list(range(n)). Every point is its own parent, so every point starts as the root of a group of one. - Create
size = [1] * n.size[r]counts the points in the group whose root isr. Only the roots' entries matter; they decide which tree goes under which. - Start
total = 0. It is the cost of the edges taken so far. - Start
used = 0. It counts the edges taken. A tree overnpoints has exactlyn - 1edges. - Loop over
edges, cheapest first, withedge.edge[0]is the cost, andedge[1]andedge[2]are the two points. - Find
rootA = self.find(parent, edge[1]). The helperfindwalks up from a point to its root. Assume it exists for now; it is written at the end. - Find
rootB = self.find(parent, edge[2]). Two points are in the same group exactly when they lead to the same root. - If
rootA != rootB, the edge joins two groups, so take it. Equal roots mean the points are already connected, and the edge would only close a cycle. - Make
rootAthe root of the larger group. Ifsize[rootA] < size[rootB], swap them withrootA, rootB = rootB, rootA. This is union by size: the smaller tree always goes under the larger. A point moves one level deeper only when its group at least doubles, so no path to a root gets longer thanlog2(n)steps. The right side of a tuple assignment is computed first, so the swap needs no third variable. - Merge:
parent[rootB] = rootA. This line is back at the indentation of the shortif, not inside it. Every point of the smaller group now reachesrootAthroughrootB. size[rootA] += size[rootB]. The merged group has the points of both.size[rootB]is never read again, becauserootBis no longer a root.total += edge[0]. This is the key line: the edge is the cheapest one left that joins two groups, so it belongs in the network.used += 1. One more edge in the network.- If
used == n - 1, returntotal. Each edge taken joined two groups into one, so aftern - 1of them the originalngroups are one. The edges left could only close cycles. - After the loop, return
total. The loop only gets here when there is one point: it has no edges, and one point costs nothing to connect. With two or more points the function always returns from inside the loop, because every pair is an edge. - Write the helper
find(self, parent, x)in the class. It returns the root ofx's group. A list is passed as the same object, so changes thatfindmakes toparentare seen byminCostConnectPoints. - Loop
while parent[x] != x. The root is the only point that is its own parent. A loop needs no call stack, however long the walk. - Set
parent[x] = parent[parent[x]]. This is path halving: each point we pass skips a level, so later walks from here take about half the steps. Together with union by size, a call costs O(α(n)) on average, which is nearly constant. - Set
x = parent[x]. It moves up to the grandparent it now points to, so each turn climbs two levels. - Return
x. The loop stops exactly at the root.
The solution in Python
class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
edges = []
for i in range(n):
for j in range(i + 1, n):
cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges.append((cost, i, j))
edges.sort()
parent = list(range(n))
size = [1] * n
total = 0
used = 0
for edge in edges:
rootA = self.find(parent, edge[1])
rootB = self.find(parent, edge[2])
if rootA != rootB:
if size[rootA] < size[rootB]:
rootA, rootB = rootB, rootA
parent[rootB] = rootA
size[rootA] += size[rootB]
total += edge[0]
used += 1
if used == n - 1:
return total
return total
def find(self, parent: List[int], x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
Python details:
- Sorting tuples.
edges.sort()sorts the list in place and returnsNone, soedges = edges.sort()would throw the list away. Tuples compare element by element, which is why the cost comes first. - Calling the helper.
findis a method, so inside the class it is called asself.find(...), withparentpassed explicitly. - Tuple swap.
rootA, rootB = rootB, rootAexchanges two variables without a temporary one. - Exact arithmetic. Manhattan distances of up to 4,000,000 are summed over up to 999 edges, and Python integers never overflow.
Complexity
Listing the edges takes O(n²), and sorting n · (n - 1) / 2 of them takes O(n² log n). The union-find work is nearly constant per edge, so it is dominated by the sort. The time is O(n² log n), and the list of edges makes the space O(n²).
Edge cases and common mistakes
- One point.
minCostConnectPoints([[5, 5]])is 0: there are no edges, and the loop is skipped. - Two points.
[[0, 0], [3, 4]]costs 7, the Manhattan distance (3 + 4), not the straight-line distance of 5. - Negative coordinates. The
abscalls make the sign of the difference irrelevant, as in the second example. - Taking every edge. Adding an edge whose ends share a root closes a cycle and adds cost. The root comparison is what prevents it.
- Comparing the points instead of the roots. Two points can be connected without being each other's parent. Always compare roots.
- Linking each point to its nearest neighbour. That can leave separate groups, and adding up those costs is not the answer.
Testing
minCostConnectPoints([[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]) -> 20
minCostConnectPoints([[3, 12], [-2, 5], [-4, 1]]) -> 18
minCostConnectPoints([[0, 0], [1, 0], [0, 1], [10, 10]]) -> 21
minCostConnectPoints([[5, 5]]) -> 0
minCostConnectPoints([[0, 0], [3, 4]]) -> 7
