Problem overview
The method minCostConnectPoints receives an array points, where each point is an [x, y] pair. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|. It returns the least total cost of connections so that you can get from any point to any other by following them. There are between 1 and 1000 points, all distinct, with coordinates up to one million in absolute value.
For [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]] the answer is 20. Four connections join the five points: [0, 0] to [2, 2] costs 4, [2, 2] to [5, 2] costs 3, [5, 2] to [7, 0] costs 4 and [2, 2] to [3, 10] costs 9. For [[3, 12], [-2, 5], [-4, 1]] the answer is 18, and for a single point it is 0.
Approach: Kruskal's algorithm on all the pairs
View every pair of points as an edge of a graph, with the Manhattan distance as its cost. That makes n · (n - 1) / 2 edges. The cheapest way to connect all the points is a minimum spanning tree: n - 1 edges that join every point with the least total cost. Any more edges would only close cycles and add cost.
Kruskal's algorithm builds it greedily. Sort the edges from the cheapest up and go through them. Take an edge if its two ends are still in different groups, which joins the two groups into one. Skip an edge whose ends are already in the same group, because it would close a cycle. After n - 1 edges taken, all the points are in one group and the loop can stop.
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 know quickly whether two points are in the same group, use union-find. Every point has a parent, and the one point that is its own parent, the root, names its group. Two points are in the same group exactly when they lead to the same root. Merging two groups hangs one root under the other.
For [[0, 0], [1, 0], [0, 1], [10, 10]] the loop over the sorted edges, written as [cost, i, j], goes like this:
take [1,0,1] total 1
take [1,0,2] total 2
skip [2,1,2]
take [19,1,3] total 21
The edge [2, 1, 2] joins points that are already connected through point 0, so it is skipped. The loop returns 21 after the third edge it takes, as n - 1 = 3.
The statement asks for O(n² log n) time and O(n²) space, which is what listing and sorting all the edges costs. Prim's algorithm is the other classic way: it grows one tree from a point and needs no sorted list of edges, but this lesson uses Kruskal.
Step by step
- Store the number of points in
n. - Create
edges, an emptynumber[][]. Each edge will be[cost, i, j], with the cost first because that is what the edges get sorted by. - Loop
iover the points. - Loop
jfromi + 1ton - 1. This lists each pair once and never pairs a point with itself. - Compute
cost:Math.absof the x difference plusMath.absof the y difference. - Push
[cost, i, j]ontoedges. - Sort the edges by cost with
edges.sort((first, second) => first[0] - second[0]). - Create
parentwithArray.from({length: n}, (_, i) => i), so every point starts as the root of a group of one. - Create
size,nones.size[r]counts the points in the group whose root isr, and decides which tree goes under which. - Declare
totalat 0: the cost of the edges taken so far. - Declare
usedat 0: the number of edges taken. A tree overnpoints has exactlyn - 1edges. - Loop over
edges, now cheapest first, withfor...of. - Find the roots.
rootAisthis.find(parent, edge[1])androotBisthis.find(parent, edge[2]), both declared withletbecause the next step may swap them. The helperfindis written at the end. - If
rootA !== rootB, the edge joins two groups, so take it. - Union by size. If
size[rootA] < size[rootB], swap the two with[rootA, rootB] = [rootB, rootA], so thatrootAis the larger group's root. - Merge: set
parent[rootB] = rootAand addsize[rootB]tosize[rootA]. - Add the edge's cost
edge[0]tototal. This is the key line. - Add 1 to
used, and ifused === n - 1, returntotalat once. The edges left could only close cycles. - After the loop, return
total. The loop gets there only for a single point, which has no edges and costs nothing. - Write
find(parent, x). Whileparent[x] !== x, setparent[x]toparent[parent[x]], thenxtoparent[x]. When the loop ends, returnx, the root.
The solution in TypeScript
class Solution {
minCostConnectPoints(points: number[][]): number {
const n = points.length;
const edges: number[][] = [];
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const cost = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
edges.push([cost, i, j]);
}
}
edges.sort((first, second) => first[0] - second[0]);
const parent: number[] = Array.from({length: n}, (_, i) => i);
const size: number[] = new Array(n).fill(1);
let total = 0;
let used = 0;
for (const edge of edges) {
let rootA = this.find(parent, edge[1]);
let rootB = this.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++;
if (used === n - 1) {
return total;
}
}
}
return total;
}
find(parent: number[], x: number): number {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
A few TypeScript details:
- Sorting needs a comparator. Without one,
sort()compares elements as strings, so for plain numbers[10, 9, 1].sort()gives[1, 10, 9]. Here the comparatorfirst[0] - second[0]returns a negative number whenfirstis cheaper, which puts it earlier. The subtraction is safe because the costs are at most 4,000,000 and anumberis a double. - Swapping with destructuring.
[rootA, rootB] = [rootB, rootA]builds an array of the two values and unpacks it back in the other order. It needsletvariables, which is why the roots aren'tconst. Array.from({length: n}, (_, i) => i)calls the arrow function once per index. The first argument is the element, unused here and named_, and the second is the index. Each call returns the index, soparent[i]starts asi.- Arrays are shared, not copied.
findreceives the sameparentarray, so its path halving changes the array thatminCostConnectPointssees. Reassigning the parameterxinsidefindchanges only its own copy of the number. this.find.findis a method, so inside another method it is called throughthis. Writing a barefind(...)would look for a function outside the class.
Complexity
Time: O(n² log n). There are about n² / 2 edges, building them costs O(n²), and sorting them costs O(n² log n). The loop over the edges then calls find twice per edge. Union by size keeps the trees shallow, with no path longer than log₂ n steps, and path halving shortens them further, so each call costs almost constant time on average. The sort dominates.
Space: O(n²). The edge list holds one array of three numbers per pair, about half a million for 1000 points. parent and size add only O(n).
Edge cases and common mistakes
- One point.
[[5, 5]]has no edges, the loop never runs, and the answer is 0. - Two points.
[[0, 0], [3, 4]]gives 7: the Manhattan distance is 3 + 4, not the straight-line 5. - Large coordinates. For
[[-1000000, -1000000], [1000000, 1000000]]the answer is 4000000. Doubles hold this exactly, so there is no overflow to guard against. - Sorting without a comparator. The edges would be compared as text, so a cost of 10 would come before 9, and the greedy choice would no longer be the cheapest edge.
- Not skipping cycles. Adding every edge whose cost is small without checking the roots counts the cost of the edge
[2, 1, 2]in the third example and gives a total above 21. - Comparing points instead of roots. Two points are connected when their roots are equal. Comparing
parent[a]withparent[b]can call two connected points different when one of them is not directly under the root, and then a cycle-closing edge gets taken.
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.
