Min Cost to Connect All Points
MediumThe problem
points[i] = [x, y] is a spot on a plane. Joining two points costs the Manhattan distance |x1 - x2| + |y1 - y2|. Return the least total cost of joining the points with wires so that every point can reach every other point.
- Example 1Input: points = [[0, 0], [2, 2], [3, 10], [5, 2], [7, 0]]Output: 20
For example join (0,0)-(2,2) for 4, (2,2)-(5,2) for 3, (5,2)-(7,0) for 4 and (2,2)-(3,10) for 9: 4 + 3 + 4 + 9 = 20.
- Example 2Input: points = [[3, 12], [-2, 5], [-4, 1]]Output: 18
(3,12)-(-2,5) costs 12 and (-2,5)-(-4,1) costs 6.
- 1 ≤ len(points) ≤ 1,000
- -1,000,000 ≤ x, y ≤ 1,000,000
- All points are different
- With one point, the answer is 0
Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.
Try it here
Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.
Hints, one at a time
Nudge
Connect everything with the least total wire — and with no cycles. That is a famous structure.
The idea
Minimum spanning tree: Prim's with a heap (start anywhere, repeatedly add the cheapest edge to a new point) or Kruskal's with union-find.
Target: O(n² log n) time
Go function shape
func minCostConnectPoints(points [][]int) intReference solution
Tested with go test. Try it yourself first, then compare.
// MinCostConnectPoints: minimum spanning tree with Prim's algorithm.
// Grow one tree: repeatedly attach the point that is cheapest to reach from the tree.
func MinCostConnectPoints(points [][]int) int {
n := len(points)
dist := make([]int, n) // cheapest known cost to attach each point to the tree
for i := range dist {
dist[i] = math.MaxInt
}
inTree := make([]bool, n)
dist[0] = 0
total := 0
for range n {
best := -1
for i := 0; i < n; i++ {
if !inTree[i] && (best == -1 || dist[i] < dist[best]) {
best = i
}
}
inTree[best] = true
total += dist[best]
for i := 0; i < n; i++ {
if !inTree[i] {
d := abs(points[best][0]-points[i][0]) + abs(points[best][1]-points[i][1])
dist[i] = min(dist[i], d)
}
}
}
return total
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}