Problem overview
The function min_cost_connect_points receives a vector of points, each an [x, y] pair. Connecting two points costs their Manhattan distance, |x1 - x2| + |y1 - y2|. The function returns the minimum total cost of connections that make all the points reachable from one another, directly or through other points.
For [[0, 0], [1, 0], [0, 1], [10, 10]] the answer is 21. The cheapest connections are [0, 0] to [1, 0] and [0, 0] to [0, 1], 1 each. Joining [1, 0] and [0, 1] (cost 2) would only repeat a link that already exists through [0, 0]. Finally [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, weighted by the Manhattan distance. There are 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 at the least total cost.
Kruskal's algorithm builds it greedily. Sort all the edges from the cheapest up. Go through them in that order and take an edge when its two ends are still in different groups, which merges the groups. If both ends are already in the same group, the edge would close a cycle and only add cost, so it is skipped. After n - 1 edges everything is one group and the algorithm can stop.
Taking the cheapest edge between two groups is always safe. The finished tree must connect 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 code uses union-find. Each group is a tree of parent links, 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. Merging by size and shortening the paths as they are walked keeps each lookup nearly constant.
The sorted edges for the example above, as [cost, i, j], are:
[1, 0, 1] take, total 1
[1, 0, 2] take, total 2
[2, 1, 2] skip: points 1 and 2 are already connected through point 0
[19, 1, 3] take, total 21
[19, 2, 3]
[20, 0, 3]
After the third edge is taken, used reaches n - 1 = 3 and the function returns 21 without looking at the last two edges.
Prim's algorithm is another classic way to find a minimum spanning tree. It grows one tree from a starting point, which suits a graph where every pair is an edge. This lesson uses Kruskal's.
Step by step
- Store the number of points in
n. - Create
edges, an emptyVec<Vec<i32>>. Each edge is a vector ofcost,iandj. The cost comes first because it is what the sort uses. - Loop over
iin0..n. With a second loop inside it, the two indexes visit every pair. - Loop over
jini + 1..n. Starting ati + 1lists each pair once and never pairs a point with itself, since connectingitojcosts the same asjtoi. - Compute the Manhattan distance as the absolute x difference plus the absolute y difference.
abs()is a method on the number, so it goes after the parenthesized difference. - Push the edge as
vec![cost, i as i32, j as i32]. A vector holds one type, so the indexes are cast to the cost's type. - Sort the edges with
sort_by_keyand a closure returningedge[0]. This is the greedy order of Kruskal's algorithm. - Create
parentas aVec<usize>holding 0 ton - 1, by collecting the range0..n. Every point starts as the root of a group of one. - Create
sizeasnones. For a rootr,size[r]is the number of points in its group. - Create
totalat 0, the cost of the edges taken so far. - Create
usedat 0, the number of edges taken. A tree overnpoints has exactlyn - 1edges. - Loop over
&edges, cheapest first. For eachedge,edge[0]is the cost andedge[1]andedge[2]are the points. - Find the root of
edge[1]withSelf::find(&mut parent, edge[1] as usize), in a mutableroot_a. The helper is written at the end. - Find the root of
edge[2]the same way, inroot_b. - Take the edge only if
root_a != root_b. Equal roots mean the edge would close a cycle. - Swap the roots if
size[root_a] < size[root_b]withstd::mem::swap, so thatroot_ais the root of the larger group. This is union by size. - Set
parent[root_b]toroot_a, hanging the smaller tree under the larger one. - Add
size[root_b]tosize[root_a]. The merged group has the points of both. - Add
edge[0]tototal. This is the key line: the edge is the cheapest one left that joins two groups. - Add 1 to
used. - Return
totalonceused == n - 1. Every point is in one group, and the edges left could only close cycles. - After the loop, return
total. The loop ends here only for a single point: it has no edges and costs nothing. - Write the helper
findinside theimpl, takingparent: &mut Vec<usize>andmut x: usize, returning the root ofx's group. - Loop while
parent[x] != x, that is, whilexis not a root. A loop needs no call stack, however long the walk. - Point
xat its grandparent:parent[x] = parent[parent[x]]. This is path halving: each node passed skips one level, so later walks are shorter. - Move
xup toparent[x]. It is the grandparent just assigned, so each turn climbs two levels. - Return
x, which is the root.
The solution in Rust
impl Solution {
fn min_cost_connect_points(points: Vec<Vec<i32>>) -> i32 {
let n = points.len();
let mut edges: Vec<Vec<i32>> = Vec::new();
for i in 0..n {
for j in i + 1..n {
let cost = (points[i][0] - points[j][0]).abs() + (points[i][1] - points[j][1]).abs();
edges.push(vec![cost, i as i32, j as i32]);
}
}
edges.sort_by_key(|edge| edge[0]);
let mut parent: Vec<usize> = (0..n).collect();
let mut size = vec![1; n];
let mut total = 0;
let mut used = 0;
for edge in &edges {
let mut root_a = Self::find(&mut parent, edge[1] as usize);
let mut root_b = Self::find(&mut parent, edge[2] as usize);
if root_a != root_b {
if size[root_a] < size[root_b] {
std::mem::swap(&mut root_a, &mut root_b);
}
parent[root_b] = root_a;
size[root_a] += size[root_b];
total += edge[0];
used += 1;
if used == n - 1 {
return total;
}
}
}
total
}
fn find(parent: &mut Vec<usize>, mut x: usize) -> usize {
while parent[x] != x {
parent[x] = parent[parent[x]];
x = parent[x];
}
x
}
}
The Rust details worth a closer look:
- The helper has no
self.findis an associated function, so it is called asSelf::find(...), with the pathSelf::naming the type theimplblock belongs to. &mut parent.findchanges the parent links while walking, so the vector is lent mutably. Insidefind,mut xonly lets the function reassign its own copy of the number. The caller's variable is untouched.std::mem::swap(&mut root_a, &mut root_b)exchanges the two values through mutable references. That is whyroot_aandroot_bare declaredlet mut.- Two integer types. Points and edges store indexes as
i32insideedges, so a vector can hold the cost and the two indexes together. Every use as an index goes throughas usize. The vectorsparentandsizeuseusize, andused == n - 1compares twousizevalues. (0..n).collect()gathers the numbers of the range into a collection. The type written onparent,Vec<usize>, tellscollectwhat to build.sort_by_keysorts in place by the key that the closure returns for each element. It is a stable sort, so edges with equal cost keep their order. Any order among equal edges gives the same minimum total.- Overflow. A single cost is at most 4,000,000 and the total of a spanning tree stays far below the
i32limit of about 2.1 billion for 1,000 points. In the-Obuilds the lessons use, an overflow would wrap silently instead of panicking.
Complexity
Time: O(n² log n). There are about n² / 2 edges, and sorting them takes O(n² log n). The loop over the sorted edges makes two find calls per edge, each nearly constant time thanks to union by size and path halving, so it costs O(n²) times a very small factor, which the sort dominates.
Space: O(n²). Storing every edge takes space proportional to the number of pairs. For 1,000 points that is just under half a million edges. parent and size add O(n).
Edge cases and common mistakes
- A single point.
[[5, 5]]returns 0. There are no edges, the loop never runs, and the finaltotalis 0. - Two points.
[[0, 0], [3, 4]]returns 7, the Manhattan distance, not the straight-line distance of 5. - Negative coordinates. The absolute value handles them:
[[3, 12], [-2, 5], [-4, 1]]returns 18. - Large coordinates.
[[-1000000, -1000000], [1000000, 1000000]]returns 4000000. The difference of two coordinates is at most 2,000,000, which fits comfortably in ani32. - Skipping the cycle check. Taking the cheapest
n - 1edges without checking the groups can pick edges that connect the same points twice. In the example, the first three edges would give a total of 4 and leave[10, 10]out. - Forgetting to stop. The loop would still be correct without the
used == n - 1exit, since later edges are all skipped, but it would do needless work on a large input. - Comparing points instead of roots. Two points are connected when their roots are equal, not when they are equal or neighbours in the
parentvector. Always callfindon both.
Testing
[[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]gives 20.[[3, 12], [-2, 5], [-4, 1]]gives 18.[[0, 0], [1, 0], [0, 1], [10, 10]]gives 21.[[5, 5]]gives 0.[[0, 0], [3, 4]]gives 7.[[-1000000, -1000000], [1000000, 1000000]]gives 4000000.
