Problem overview
The function minCostConnectPoints receives a vector points where each point is 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 connects all the points, meaning you can get from any point to any other by following connections.
For [[0, 0], [1, 0], [0, 1], [10, 10]] the answer is 21. The two cheapest connections, [0, 0] to [1, 0] and [0, 0] to [0, 1], cost 1 each. Connecting [1, 0] to [0, 1] (cost 2) would only join two points that are already linked. Then [10, 10] joins through [1, 0] at cost 9 + 10 = 19, for a total of 1 + 1 + 19.
Approach: Kruskal's algorithm
Treat 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 everything with the least total cost, and no cycle.
Kruskal's algorithm sorts the edges from cheapest to dearest and goes through them. It takes an edge when its two ends are still in different groups, which merges the two groups. If the ends are already in the same group, the edge would only close a cycle and add cost, so it is skipped. After n - 1 edges taken, everything is 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 swapping a dearer edge for the cheaper one would give a tree that costs no more. Sorting the edges takes O(n * n * log n), which is the time the statement allows, and storing them takes O(n * n) space.
To ask "are these two points in the same group?" quickly, the code uses union-find. Each point has a parent, and a point that is its own parent is the root that names its group. Two points are in the same group exactly when they lead to the same root. Two tricks keep the trees shallow: union by size hangs the smaller tree under the larger, and path halving shortens paths while walking up.
The six edges of the example above, as {cost, i, j} after sorting:
{1,0,1} {1,0,2} {2,1,2} {19,1,3} {19,2,3} {20,0,3}Kruskal takes the first two, skips {2,1,2} because points 1 and 2 are already joined through point 0, takes {19,1,3}, and stops with three edges. The total is 1 + 1 + 19 = 21.
Prim's algorithm is the other classic approach: it grows one tree from a starting point. This lesson uses Kruskal.
Step by step
- Store the number of points in
n. - Create
edges, avector<array<int, 3>>. Each edge is three ints,{cost, i, j}, with the cost first because that is what the edges are sorted by. Anarray<int, 3>keeps its three numbers inside itself, so building and sorting half a million of them is faster than with small vectors. - Loop over
i, and inside it overjfromi + 1. This lists each pair once and never pairs a point with itself. - Compute
costasabsof the x difference plusabsof the y difference. The absolute value makes each difference a distance whichever point is further left or lower. - Add
{cost, i, j}toedgeswithpush_back. The braces build the array in place. - Sort
edgesby cost withsortand a lambda comparingfirst[0] < second[0]. The¶meters compare the edges where they are instead of copying them. - Set up union-find.
parentis avector<int>of sizen, andsizeis avector<int>ofnones, the number of points in the group of each root. - Make every point its own parent in a loop. Each point starts as the root of a group of one.
- Create
totalandused, both 0: the cost so far and the number of edges taken. - Loop over the sorted edges with
auto& edge.edge[0]is the cost, andedge[1]andedge[2]are the points. - Find both roots,
rootAandrootB, with the helperfind, which is written at the end. - If the roots differ, the edge joins two groups. Swap them if needed so that
rootAhas the largersize, then setparent[rootB]torootAand addsize[rootB]tosize[rootA]. - Add
edge[0]tototaland incrementused. This is the key line: the edge is the cheapest one left that joins two groups. - When
used == n - 1, returntotal. Every point is in one group, and the remaining edges could only close cycles. - After the loop, return
total. It is reached only with a single point, which has no edges and costs nothing. - Write
find. Whileparent[x] != x, setparent[x]toparent[parent[x]]and then movextoparent[x]. When the loop ends,xis the root.
The solution in C++
class Solution {
public:
int minCostConnectPoints(vector<vector<int>>& points) {
int n = points.size();
vector<array<int, 3>> edges;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int cost = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
edges.push_back({cost, i, j});
}
}
sort(edges.begin(), edges.end(), [](auto &first, auto &second) {
return first[0] < second[0];
});
vector<int> parent(n);
vector<int> size(n, 1);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int total = 0;
int used = 0;
for (auto& edge : edges) {
int rootA = find(parent, edge[1]);
int rootB = find(parent, edge[2]);
if (rootA != rootB) {
if (size[rootA] < size[rootB]) {
swap(rootA, rootB);
}
parent[rootB] = rootA;
size[rootA] += size[rootB];
total += edge[0];
used++;
if (used == n - 1) {
return total;
}
}
}
return total;
}
int find(vector<int>& parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
};
The C++ details worth a closer look:
findis declared after it is used. Inside a class, a member function can call another member function that is written further down, because the compiler reads the whole class body before it checks the function bodies.- Reference parameter.
findtakesvector<int>& parent. Without the&each call would receive a copy of the vector, and the path halving would change the copy instead of the real one. autoin a lambda.[](auto &first, auto &second)is a generic lambda, which works since C++14. The compiler deduces that both parameters arearray<int, 3>.- Ties in the sort. Comparing only
first[0] < second[0]orders edges by cost, and edges of equal cost can come in any order. That is fine here: the total of a minimum spanning tree does not depend on how ties are broken. - A local named
size. The vectorsizehides the standard library'sstd::sizefunction insideminCostConnectPoints. That works, but a name such asgroupSizewould be clearer. intis enough. One edge costs at most 4,000,000, and with at most 1000 points the cheapest tree is far below the 32-bit limit. The tree takes onlyn - 1edges, so the total stays small. Adding up every edge of the list would not fit.
Complexity
Time: O(n * n * log n). Building the edges takes O(n * n). Sorting about n * n / 2 edges takes O(n * n * log n). Each edge then makes two find calls, which cost almost constant time on average thanks to union by size and path halving.
Space: O(n * n). The edge list holds one entry per pair of points, about 500,000 entries for 1000 points. parent and size add O(n).
Edge cases and common mistakes
- One point.
[[5, 5]]returns 0: no edges exist, the loop does nothing and the finalreturn totalruns. - Two points.
[[0, 0], [3, 4]]returns 7, the Manhattan distance, not the straight-line 5. - Far-apart points.
[[-1000000, -1000000], [1000000, 1000000]]returns 4000000. The coordinates are subtracted beforeabs, and the differences fit in anint. - Skipping cycle edges. Without the
rootA != rootBtest, every edge would be added and the total would be the sum of all of them. - Counting edges. A tree on
npoints hasn - 1edges. Waiting fornedges never succeeds, so the loop would run through every remaining edge for nothing. The early return is an optimisation, but only when the count is right. - Pairing from 0. If
jstarted at 0, every pair would be listed twice and each point would pair with itself at cost 0. - Passing
parentby value. The code still compiles, but it is slow and path halving no longer changes the real vector.
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.
