Problem overview
The method minCostConnectPoints(points) receives an array of n points, each an [x, y] pair. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|: the distance along grid lines, like a taxi driving through city blocks. The method returns the minimum total cost of connections that link all the points, so that you can get from any point to any other by following connections.
For points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]] the answer is 20: the connections [0,0]-[2,2] (cost 4), [2,2]-[5,2] (3), [5,2]-[7,0] (4) and [2,2]-[3,10] (9) add up to 20. For [[3, 12], [-2, 5], [-4, 1]] the answer is 18, and for [[0, 0], [1, 0], [0, 1], [10, 10]] it is 21.
Approach: sort all the connections, take the cheap useful ones
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 the points is a minimum spanning tree: n - 1 edges that connect every point, with the least total cost. A network with fewer edges leaves a point cut off, and one with more has a cycle that only adds cost.
Kruskal's algorithm builds it greedily. Sort the edges from the cheapest up. Go through them in that order and take an edge only if its two ends are still in different groups, which joins the two groups into one. An edge whose ends are already in the same group would close a cycle, so it is skipped. After n - 1 edges taken, every point is in one group and the algorithm 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 for that, swapping in the cheaper one would give a tree that costs no more.
To ask whether two points are in the same group, the lesson uses union-find. Each point links to a parent, and the root, the one point that is its own parent, names the group. Two points are in the same group exactly when they lead to the same root.
For the third example, 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]]
The first two edges join points 0, 1 and 2, for 2 in all. The edge [2, 1, 2] links two points that are already connected through point 0, so it is skipped. The edge [19, 1, 3] joins the point [10, 10], and that was the third edge taken, so used reaches n - 1 = 3. The total is 1 + 1 + 19 = 21.
Sorting about n²/2 edges takes O(n² log n) time and keeping them takes O(n²) space. Prim's algorithm, which grows one tree from a starting point, is the other classic way to solve this problem.
Step by step
- Store
n, the number of points. - Create
edges, an empty array. Each edge will be[cost, i, j]. The cost comes first because it is what the edges are sorted by. - Loop over the points with
i, and inside it loop withjfromi + 1. Starting ati + 1lists each pair once and never pairs a point with itself. - Compute the cost as
Math.absof the x difference plusMath.absof the y difference. The absolute value makes each difference a distance, whichever point is further left or lower. - Push
[cost, i, j]ontoedges. - Sort the edges by cost with
edges.sort((first, second) => first[0] - second[0]). A negative result putsfirstbeforesecond. - Set up union-find:
parentbuilt withArray.from({length: n}, (_, i) => i), so every point starts as its own root, andsizeasnones, the number of points in the group of each root. - Declare
totalandusedat 0 withlet: the cost so far and the number of edges taken. - Loop over the sorted edges with
for...of. - Find both roots:
rootA = this.find(parent, edge[1])androotB = this.find(parent, edge[2]), declared withletbecause they may be swapped. - Skip equal roots. Only when
rootA !== rootBdoes the edge join two groups. - Union by size: if
size[rootA] < size[rootB], swap the two roots with a destructuring assignment, so thatrootAis the root of the larger group. - Merge: set
parent[rootB]torootA, and addsize[rootB]tosize[rootA]. - Count the edge: add
edge[0]tototaland doused++. - Stop early: once
used === n - 1, returntotal. The edges left could only close cycles. - Return
totalafter the loop. It is reached only for a single point, which has no edges and costs nothing. - Write the helper
find(parent, x)inside the class: whileparent[x] !== x, setparent[x]toparent[parent[x]]and thenxtoparent[x]. Then returnx.
The solution in JavaScript
class Solution {
minCostConnectPoints(points) {
const n = points.length;
const edges = [];
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 = Array.from({length: n}, (_, i) => i);
const size = 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, x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
The JavaScript details worth knowing:
sortneeds a comparator. With no function,sortcompares elements as strings:[10, 9, 1].sort()gives[1, 10, 9]. For edges, which are arrays, it compares their text forms, so[[10,0,1],[9,1,2],[1,2,3]].sort()gives[[1,2,3],[10,0,1],[9,1,2]]. The comparatorfirst[0] - second[0]returns a negative, zero or positive number, which is allsortneeds. Subtracting is safe here because the costs are small integers.- Swapping with destructuring.
[rootA, rootB] = [rootB, rootA]builds an array of the two values in the other order and unpacks it into the variables, with no temporary. That is whyrootAandrootBarelet. Array.fromwith a function.Array.from({length: n}, (_, i) => i)calls the function once per index. The first parameter is the element, which does not exist here, so it is named_and ignored.- Methods called through
this.findis a method of the class, sominCostConnectPointscalls it asthis.find(...). A barefind(...)would look for a variable namedfindand fail. - Arrays are shared, not copied.
findreceives the sameparentarray, so its changes (path halving) are visible to the caller. - Path halving. Each step points
xat its grandparent, so later walks from the same point take about half the steps. The loop needs no recursion, so there is no call stack to overflow however long the walk is. Together with union by size, each call is almost constant time.
Complexity
Time: O(n² log n). Building the edges takes O(n²). Sorting them takes O(n² log n), which dominates. The loop over the edges makes two find calls per edge, each nearly constant time.
Space: O(n²). The edges array holds n · (n - 1) / 2 entries, about half a million for 1,000 points. parent and size add only O(n).
Edge cases and common mistakes
- A single point.
[[5, 5]]returns 0. There are no edges, so the loop does nothing andtotalstays 0.used === n - 1would be0 === 0, but it is never tested because no edge exists. - Two points.
[[0, 0], [1, 1]]returns 2.[[-1000000, -1000000], [1000000, 1000000]]returns 4000000, the largest possible single edge. - Negative coordinates. The absolute value makes every difference non-negative, so the order of the points never matters.
- Sorting without a comparator. The edges would be ordered as text, so a cost of 10 would come before 9, and the greedy choice would be wrong.
- Skipping the root check. Taking every cheap edge, including ones inside a group, adds cycles and a larger total.
- Forgetting
this.beforefind. The call fails with aReferenceError, because no variable namedfindexists. - Comparing points instead of roots. Two points in the same group can have different parents. Only their roots tell whether they are connected.
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], [1, 1]]gives2.[[-1000000, -1000000], [1000000, 1000000]]gives4000000.
