Problem overview
The method minCostConnectPoints(int[][] points) receives n distinct points [x, y]. Connecting two points costs their Manhattan distance, |xi - xj| + |yi - yj|: the distance along the grid lines, as a taxi drives through city blocks. The method returns the minimum total cost so that you can get from any point to any other by following connections.
For [[0,0],[2,2],[3,10],[5,2],[7,0]] the answer is 20. Four connections join the five points: [0,0]-[2,2] costs 4, [2,2]-[5,2] costs 3, [5,2]-[7,0] costs 4 and [2,2]-[3,10] costs 9. The total is 4 + 3 + 4 + 9 = 20. For [[3,12],[-2,5],[-4,1]] the answer is 18.
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. The cheapest way to connect all points is a minimum spanning tree: n - 1 edges that join every point, with the least total cost.
Kruskal's algorithm sorts the edges from cheapest up and takes each edge whose two ends are still in different groups, which merges the two groups into one. An edge whose ends are already in the same group would only close a cycle, so it is skipped. 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 would give a tree that costs no more.
To ask "are these two points in the same group?" quickly, the solution uses union-find. Each group is a tree in which every point links to a parent, and the root, the only point that is its own parent, names the group. Two points are in the same group exactly when they lead to the same root.
Take [[0,0],[1,0],[0,1],[10,10]]. Sorted by cost, the edges as [cost, i, j] come out as:
[1, 0, 1]
[1, 0, 2]
[2, 1, 2]
[19, 1, 3]
[19, 2, 3]
[20, 0, 3]
The first two edges join points 0, 1 and 2, at cost 1 each. The edge [2, 1, 2] links two points already in one group, so it is skipped. The edge [19, 1, 3] brings in point 3. That makes three edges, n - 1, and the total is 1 + 1 + 19 = 21.
The sort of about n²/2 edges takes O(n² log n) time, and storing them takes O(n²) space, which is what the statement allows for n up to 1000. Prim's algorithm, which grows one tree from a single point, is the other classic way to build a minimum spanning tree.
Step by step
- Store the number of points in
n. - Create
edgesas aList<int[]>, anArrayList. Each edge is an array{cost, i, j}. The cost comes first because the edges get sorted by it. - List every pair once. The outer loop runs
ifrom 0 ton - 1, and the inner loop runsjfromi + 1. Starting ati + 1never pairs a point with itself and lists each pair once, because connectingitojcosts the same asjtoi. - Compute the cost as
Math.absof the x difference plusMath.absof the y difference, then addnew int[]{cost, i, j}toedges. - Sort the edges by cost with
edges.sortand a lambda that returnsfirst[0] - second[0]. A negative result putsfirstin front. A cost is at most 4,000,000, so the subtraction can't overflow. - Set up union-find. Create
parentandsize, bothintarrays of lengthn.parent[x]is the parent of pointx, andsize[r]counts the points in the group rooted atr. - Start every point alone. A loop sets
parent[i] = iandsize[i] = 1. Newintarrays hold zeros, so the sizes must be set. - Create
totalandused, both 0: the cost of the edges taken and how many edges the network has. - Walk the sorted edges. For each
edge, find the root ofedge[1]inrootAand ofedge[2]inrootB, using the helperfind, written at the end. - Skip same-group edges. If
rootA == rootB, the edge would close a cycle and only add cost. - Merge by size. Otherwise, if
size[rootA] < size[rootB], swap the two roots using a temporary variable, sorootAis the root of the larger group. Then setparent[rootB] = rootAand addsize[rootB]tosize[rootA]. The smaller tree always goes under the larger one, which keeps the trees shallow. - Take the edge. Add
edge[0]tototaland doused++. - Stop early. Once
used == n - 1, all points are in one group, so returntotal. The edges left could only close cycles. - After the loop, return
total. The loop gets there only for a single point: there are no edges and nothing to pay. - Write
find. It walks up whileparent[x] != x. Inside the loop,parent[x] = parent[parent[x]]makesxskip to its grandparent (path halving), thenx = parent[x]climbs. The loop ends at the root, which is returned.
The solution in Java
class Solution {
public int minCostConnectPoints(int[][] points) {
int n = points.length;
List<int[]> edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int cost = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
edges.add(new int[]{cost, i, j});
}
}
edges.sort((first, second) -> first[0] - second[0]);
int[] parent = new int[n];
int[] size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
int total = 0;
int used = 0;
for (int[] edge : edges) {
int rootA = find(parent, edge[1]);
int rootB = find(parent, edge[2]);
if (rootA != rootB) {
if (size[rootA] < size[rootB]) {
int temp = rootA;
rootA = rootB;
rootB = temp;
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
total += edge[0];
used++;
if (used == n - 1) {
return total;
}
}
}
return total;
}
int find(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
The Java details worth a closer look:
- Arrays are passed by reference.
findreceives the very arrayparent, so when it changes an entry,minCostConnectPointssees the change. The parameterxis a copy of a number: assigning to it insidefindchanges only the local copy. - The comparator lambda.
(first, second) -> first[0] - second[0]is aComparator<int[]>. Subtracting is safe only because the costs are small:Integer.MAX_VALUE - (-5)wraps around to-2147483644, so with huge values you would useInteger.compare(first[0], second[0])instead. - Swapping needs a temporary variable. Assigning
rootA = rootBfirst would lose the oldrootA, so it is saved intemp. - A loop instead of recursion.
finduses awhileloop, so a long chain of parents can't overflow the call stack. - Calling
findfrom an instance method.findis an instance method in the same class, so the callfind(parent, edge[1])needs no object name. intcosts. One cost is at most 4,000,000, so it fits easily in anint: two points at(-1000000, -1000000)and(1000000, 1000000)cost 4000000. The runningtotalis aninttoo, which suits a minimum tree: it uses only the cheapest connections, not every edge.
Complexity
Time: O(n² log n). Building the edges takes O(n²). Sorting about n²/2 edges takes O(n² log n). The union-find calls cost almost constant time each, thanks to union by size and path halving.
Space: O(n²). The edge list holds n · (n - 1) / 2 small arrays. parent and size add only O(n).
Edge cases and common mistakes
- One point.
[[5,5]]returns 0: there are no edges, the loop doesn't run andtotalis 0. - Two points.
[[0,0],[3,4]]returns 7, the Manhattan distance 3 + 4, not the straight-line distance 5. - Negative coordinates. Differences are wrapped in
Math.abs, so[[3,12],[-2,5],[-4,1]]gives 18. - Taking a cycle edge. In
[[0,0],[1,0],[0,1],[10,10]]the edge between[1,0]and[0,1]costs 2 but joins two points already connected through[0,0]. Taking it would give 23 instead of 21. - Counting an edge without merging. Adding the cost but forgetting to set
parent[rootB]leaves the groups apart, and the next edges are judged wrongly. - Using
parent[x]as the root. A point's parent is not its root unless it is the root itself, so always callfind.
Testing
[[0,0],[2,2],[3,10],[5,2],[7,0]]gives20.[[3,12],[-2,5],[-4,1]]gives18.[[0,0],[1,0],[0,1],[10,10]]gives21.[[5,5]]gives0.[[0,0],[3,4]]gives7.[[-1000000,-1000000],[1000000,1000000]]gives4000000.
