Connect every point at the least cost
You are given distinct points on a plane, points[i] = [x, y]. Connecting points
i and j costs their Manhattan distance |xi − xj| + |yi − yj|.
Return the minimum total cost to make every point reachable from every other: each pair must be joined by
exactly one path of connections.
Examples
| Input | Output | Why |
|---|---|---|
points = [[0,0],[2,2],[3,10],[5,2],[7,0]] | 20 | Connect (0,0)–(2,2), (2,2)–(5,2), (5,2)–(7,0) and (2,2)–(3,10): 4 + 3 + 4 + 9. |
points = [[3,12],[-2,5],[-4,1]] | 18 | (-4,1)–(-2,5) costs 6, (-2,5)–(3,12) costs 12. |
points = [[0,0]] | 0 | One point needs no connection. |
Constraints
- 1 ≤ points.length ≤ 1000
- −10⁶ ≤ x, y ≤ 10⁶
- All points are distinct
Hints
Hint 1
Exactly one path between every pair means the connections form a tree: you want a minimum spanning tree.
Hint 2
Every pair of points is a possible edge: about n²/2 of them. Sorting them all for Kruskal is possible but heavy.
Hint 3
Prim without a heap: keep for each point outside the tree its cheapest connection to the tree, pick the smallest, then update the others. O(n²) and no edge list.
Where people lose marks
- Building all n²/2 edges and sorting them: correct, but 500,000 edges for n = 1000 and much slower.
- Using Euclidean distance instead of Manhattan distance.
- Overflow: a single distance can reach 4 · 10⁶ and the total 4 · 10⁹, beyond a 32-bit integer.
Dry run on [[0,0],[2,2],[3,10],[5,2],[7,0]]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 8
Points A=(0,0), B=(2,2), C=(3,10), D=(5,2), E=(7,0); every pair is an edge weighted by Manhattan distance. Sort the edges by weight: 3, 4, 4, 7, 7, 7, 9, 10, 13, 14. Every node is its own group.
-
Step 2 / 8total3edges1
B–D (3): it joins two different groups, so take it. Total 3.
-
Step 3 / 8total7edges2
A–B (4): it joins two different groups, so take it. Total 7.
-
Step 4 / 8total11edges3
D–E (4): it joins two different groups, so take it. Total 11.
-
Step 5 / 8total11edges3
A–D (7): both ends are already connected by chosen edges. Taking it would close a cycle: skip.
-
Step 6 / 8total11edges3
A–E (7): both ends are already connected by chosen edges. Taking it would close a cycle: skip.
-
Step 7 / 8total11edges3
B–E (7): both ends are already connected by chosen edges. Taking it would close a cycle: skip.
-
Step 8 / 8total20edges4
B–C (9): it joins two different groups, so take it. Total 20. 4 edges join all 5 nodes: that is a minimum spanning tree, weight 20.
How to think about it
The cheapest set of connections that joins everything with exactly one path between any two points is a minimum spanning tree of the complete graph on the points, with Manhattan distances as weights.
That graph has about n²/2 edges, so the right tool is the array form of Prim's algorithm. Keep
best[v], the cheapest edge from point v to any point already in the tree. Start with point 0 in the
tree. Each round, add the outside point with the smallest best, add that cost to the total, and
lower best[w] for every other outside point w using its distance to the newly added point. n rounds
of O(n) work give O(n²) time and O(n) memory, with no edge list at all.
Complexity. Time O(n²) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def min_cost_connect(points):
n = len(points)
INF = float('inf')
best = [INF] * n # cheapest connection from each point to the tree
in_tree = [False] * n
best[0] = 0
total = 0
for _ in range(n):
u = min((v for v in range(n) if not in_tree[v]), key=lambda v: best[v])
in_tree[u] = True
total += best[u]
ux, uy = points[u]
for v in range(n): # the new tree point may offer a cheaper connection
if not in_tree[v]:
d = abs(ux - points[v][0]) + abs(uy - points[v][1])
if d < best[v]:
best[v] = d
return total#include <climits>
#include <cstdlib>
#include <vector>
long long solve(const std::vector<std::vector<int>>& points) {
const int n = points.size();
std::vector<long long> best(n, LLONG_MAX); // cheapest connection to the tree
std::vector<bool> inTree(n, false);
best[0] = 0;
long long total = 0;
for (int round = 0; round < n; ++round) {
int u = -1;
for (int v = 0; v < n; ++v)
if (!inTree[v] && (u < 0 || best[v] < best[u])) u = v;
inTree[u] = true;
total += best[u];
for (int v = 0; v < n; ++v) {
if (inTree[v]) continue;
long long d = std::llabs((long long)points[u][0] - points[v][0]) + std::llabs((long long)points[u][1] - points[v][1]);
if (d < best[v]) best[v] = d;
}
}
return total;
}class Solution {
public long minCostConnect(int[][] points) {
int n = points.length;
long[] best = new long[n]; // cheapest connection to the tree
java.util.Arrays.fill(best, Long.MAX_VALUE);
boolean[] inTree = new boolean[n];
best[0] = 0;
long total = 0;
for (int round = 0; round < n; round++) {
int u = -1;
for (int v = 0; v < n; v++)
if (!inTree[v] && (u < 0 || best[v] < best[u])) u = v;
inTree[u] = true;
total += best[u];
for (int v = 0; v < n; v++) {
if (inTree[v]) continue;
long d = Math.abs((long) points[u][0] - points[v][0]) + Math.abs((long) points[u][1] - points[v][1]);
if (d < best[v]) best[v] = d;
}
}
return total;
}
}function minCostConnect(points) {
const n = points.length;
const best = new Array(n).fill(Infinity); // cheapest connection to the tree
const inTree = new Array(n).fill(false);
best[0] = 0;
let total = 0;
for (let round = 0; round < n; round++) {
let u = -1;
for (let v = 0; v < n; v++) if (!inTree[v] && (u < 0 || best[v] < best[u])) u = v;
inTree[u] = true;
total += best[u];
for (let v = 0; v < n; v++) {
if (inTree[v]) continue;
const d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);
if (d < best[v]) best[v] = d;
}
}
return total;
}fn solve(points: &[[i64; 2]]) -> i64 {
let n = points.len();
let mut best = vec![i64::MAX; n]; // cheapest connection to the tree
let mut in_tree = vec![false; n];
best[0] = 0;
let mut total = 0;
for _ in 0..n {
let u = (0..n).filter(|&v| !in_tree[v]).min_by_key(|&v| best[v]).unwrap();
in_tree[u] = true;
total += best[u];
for v in 0..n {
if !in_tree[v] {
let d = (points[u][0] - points[v][0]).abs() + (points[u][1] - points[v][1]).abs();
best[v] = best[v].min(d);
}
}
}
total
}import Data.List (foldl')
import qualified Data.Map.Strict as M
solve :: [[Int]] -> Int
solve points = go (M.fromList [(i, if i == 0 then 0 else maxBound) | i <- [0 .. n - 1]]) 0
where
n = length points
pt = M.fromList (zip [0 ..] points)
dist a b = let [x1, y1] = pt M.! a; [x2, y2] = pt M.! b in abs (x1 - x2) + abs (y1 - y2)
-- the map holds the points outside the tree and their cheapest connection to it
go outside total
| M.null outside = total
| otherwise =
let (u, cost) = M.foldlWithKey' (\acc k c -> if c < snd acc then (k, c) else acc) (-1, maxBound) outside
rest = M.delete u outside
in go (M.mapWithKey (\v c -> min c (dist u v)) rest) (total + cost)Variants to try
- Some connections already exist for free: start union-find with them merged, then run Kruskal.
- Return the connections themselves, not just the total.
- n = 10⁵ points: the complete graph is too big; for Manhattan distance only O(n) candidate edges are needed (a sweep by octants).
Next problems
The connection that closes a loop
A tree had one extra edge added. Return the edge that can be removed to make it a tree again: the first one union-find cannot merge.
Open the problem → Medium20 minMoving cables to connect a network
Count the separate groups with a disjoint-set structure; spare cables are the edges that close a cycle.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem →Write a solution and run it against the real test table.
Keep going
The connection that closes a loop
A tree had one extra edge added. Return the edge that can be removed to make it a tree again: the first one union-find cannot merge.
Open the problem → Medium20 minMoving cables to connect a network
Count the separate groups with a disjoint-set structure; spare cables are the edges that close a cycle.
Open the problem → Easy12 minCount the islands in a grid
Every unvisited land cell starts a new island; flood it so it is never counted again. The first graph problem most interviews ask.
Open the problem → GraphsThe pattern behind it
Grids, networks and dependencies are all graphs. Breadth-first search finds shortest paths, depth-first search and union-find find what is connected, Dijkstra handles weighted edges, and a queue of nodes with no remaining prerequisites gives an order.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.