Min Cost to Connect All Points
Medium · Advanced Graphs · Array · Graph · Union Find · Minimum Spanning Tree
Problem
You are given points, where points[i] = [x_i, y_i] is a point on a grid. Linking two points costs their Manhattan distance, |x_i - x_j| + |y_i - y_j|.
Return the minimum total cost of links so that every point can reach every other point. The cheapest such set of links never contains a cycle: it is a minimum spanning tree.
Examples
Input: points = [[0,0],[3,0],[3,4],[0,5]] Output: 11
Link [0,0]-[3,0] for 3, [3,0]-[3,4] for 4 and [3,4]-[0,5] for 4: 11 in all.
Input: points = [[1,1],[2,2]] Output: 2
One link of cost |1 - 2| + |1 - 2| = 2.
Input: points = [[5,5]] Output: 0
A single point needs no links.
Constraints
- 1 <= len(points) <= 1000
- -10^6 <= x_i, y_i <= 10^6
- All points are distinct.
Approaches
- Kruskal over every pair — time O(n² log n), space O(n²)
Follow-up
With n up to 1000 the complete graph has about 500,000 edges, so the array version of Prim (no heap, O(n²)) beats both Kruskal and heap-based Prim. For much larger n, Manhattan distance has a special trick: only a few nearest neighbours in each of eight directions can be in the tree, which leaves O(n) candidate edges. The use cases below give the edges explicitly, as roads and pipes.
Related problems
Start free on Cariara · Coding problems · System design studio
