Min Cost to Connect All Points
Problem statement
Racks sit on a data-centre floor at integer grid positions points[i] = [x, y]. Cable runs only along the aisles, so a cable between two racks costs their Manhattan distance, |x1 - x2| + |y1 - y2|.
Return the minimum total cable cost so that every rack is connected to every other one, directly or through other racks. All positions are distinct.
Connecting everything as cheaply as possible, with no need for redundant links, is exactly a minimum spanning tree over the complete graph of points.
Examples
Example 1
Input: points = [[0,0],[1,1],[4,0],[4,3]]
Output: 9
Explanation: Link [0,0]-[1,1] (2), [4,0]-[4,3] (3) and [0,0]-[4,0] (4). Nothing cheaper joins the two pairs.
Example 2
Input: points = [[7,-3]]
Output: 0
Explanation: A single rack needs no cable.
Hints
Approach
Prim's algorithm with an array. Keep dist[i], the cheapest cable from point i to the tree built so far. Start the tree at point 0 (dist[0] = 0).
Repeat n times: pick the outside point with the smallest dist, add that cost to the total and move the point into the tree, then update every outside point's dist with its distance to the new point.
Each round is one linear scan, so the total is O(n²), which is optimal for a complete graph because there are that many edges to look at anyway. No edge list is stored, so memory stays O(n). A heap-based Prim would be O(n² log n) here, slower, because the graph is dense.
O(n²)Space O(n)def min_cost_connect_points(points): n = len(points) INF = float("inf") dist = [INF] * n dist[0] = 0 in_tree = [False] * n total = 0 for _ in range(n): u = min((i for i in range(n) if not in_tree[i]), key=lambda i: dist[i]) in_tree[u] = True total += dist[u] ux, uy = points[u] for v in range(n): if not in_tree[v]: d = abs(ux - points[v][0]) + abs(uy - points[v][1]) if d < dist[v]: dist[v] = d return total print(min_cost_connect_points([[0, 0], [1, 1], [4, 0], [4, 3]]))print(min_cost_connect_points([[7, -3]]))Follow-up questions
- Some racks already have a cable between them for free. How do you account for existing links? (Union them first, then run Kruskal.)
- What if the budget allows one redundant cable for resilience: which extra cable gives the most benefit?
Frequently asked questions
Minimum spanning trees are the textbook model for connecting sites, racks or regions with the least cabling or link cost. It is also a clean way to test whether you know both Kruskal and Prim and can pick between them based on graph density, which is the kind of trade-off reasoning infra interviews like.
For a sparse graph given as an edge list, Kruskal with union-find. For a complete graph like this one, where every pair is an edge, array-based Prim is faster and uses less memory. Saying why, in one sentence, is often worth as much as the code.
The total cost is. The tree itself may not be when several edges tie, as in the first example where two different 4-cost links could join the pairs. Any minimum spanning tree gives the same total.