You are given points, an array of distinct points on a 2-D plane where points[i] = [xi, yi].
The cost of connecting two points is the Manhattan distance between them: |xi - xj| + |yi - yj|.
Return the minimum total cost to connect all the points so that there is exactly one path between any two of them. (In graph terms: the weight of a minimum spanning tree over the points.)
Example
Connecting (0,0)-(2,2)=4, (2,2)-(5,2)=3, (5,2)-(7,0)=4, (5,2)-(3,10)=... the minimum spanning tree totals 20.
Constraints
- 1 <= points.length <= 1000
- -10^6 <= xi, yi <= 10^6
- All pairs (xi, yi) are distinct.
Intuition
We must connect every point into one network at minimum total Manhattan-distance cost — the weight of a minimum spanning tree over the complete graph of points. A naïve greedy that just repeatedly adds the globally cheapest edge (ignoring structure) risks forming cycles or leaving the tree disconnected; the honest brute force is to build all O(n²) edges, sort them, and add edges that don't create a cycle.
function minCostConnectPoints(points) {
const n = points.length;
const edges = [];
// Every pair is a candidate edge, weighted by Manhattan distance.
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
edges.push([Math.abs(points[i][0]-points[j][0]) + Math.abs(points[i][1]-points[j][1]), i, j]);
edges.sort((a, b) => a[0] - b[0]); // cheapest first
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x) => parent[x] === x ? x : (parent[x] = find(parent[x]));
let total = 0, used = 0;
for (const [w, i, j] of edges) {
const ri = find(i), rj = find(j);
if (ri === rj) continue; // would form a cycle — skip
parent[ri] = rj; total += w; used++; // safe edge: add it
if (used === n - 1) break; // tree complete
}
return total;
}Materialising and sorting all n² edges is the cost. Can we do better?
The key observation: the graph is complete — every pair is connectable — so we never need the edge list at all. Prim's algorithm grows one tree outward: keep minDist[i] = the cheapest edge from point i to the tree so far, repeatedly pull in the nearest outside point, add its cost, and relax every remaining point against its distance to the newly-added one. For a dense graph this O(n²) scan-and-relax beats sorting O(n²) edges. Both Prim and Kruskal are greedy MST builders.
A point cloud and its spanning tree don't animate on a lane. The static graph shows the MST edges chosen for the example points [[0,0],[2,2],[3,10],[5,2],[7,0]] (labelled by index).
- An MST always has exactly `n − 1` edges and no cycles. Prim adds exactly one point (and one edge) per step after the seed, so it can't over- or under-connect.
- The dense O(n²) Prim is deliberate. With a complete graph, the heap-based O(E log V) Prim degrades to O(n² log n); the plain array scan is simpler and asymptotically better here.
Optimization
Prim's algorithm
Every pair of points is connectable, so the graph is complete and the answer is the weight of its minimum spanning tree. Prim's algorithm grows the tree one point at a time, always adding the cheapest edge that reaches a point not yet in the tree.
Keep minDist[i] = the cheapest known edge connecting point i to the growing tree (0 for the seed point, Infinity otherwise) and a inTree flag per point. Repeat n times: pick the not-yet-added point with the smallest minDist, add its cost to the total, mark it in the tree, then relax every other outside point's minDist against the Manhattan distance to the just-added point.
This dense O(n²) formulation (scan all points to find the minimum, then relax all points) avoids building the O(n²) edge list explicitly and is the right shape for a complete graph. Space is O(n).
function minCostConnectPoints(points) {
const n = points.length;
if (n <= 1) return 0; // nothing to connect
const inTree = new Array(n).fill(false);
// minDist[i] = cheapest edge from point i to the tree built so far.
const minDist = new Array(n).fill(Infinity);
minDist[0] = 0; // seed the tree at point 0
let total = 0;
for (let step = 0; step < n; step++) {
// Pick the cheapest point not yet in the tree.
let u = -1;
for (let i = 0; i < n; i++) {
if (!inTree[i] && (u === -1 || minDist[i] < minDist[u])) u = i;
}
inTree[u] = true;
total += minDist[u]; // pay for the edge that pulled u in
// Relax every outside point against its distance to the newly added 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 < minDist[v]) minDist[v] = d;
}
}
return total;
}Complexity analysis
Time complexity: O(n²). Here's why:
- Prim runs
nrounds; each round scans all points to find the nearest outside one (O(n)) and relaxes all points against it (O(n)).
That's n × O(n) = O(n²) — and for a complete graph this beats materialising and sorting the O(n²) edges that Kruskal needs (O(n² log n)).
Space complexity: O(n). Here's why:
- The
minDistandinTreearrays are one entry per point,O(n). - No explicit edge list is built — distances are computed on the fly.
So the auxiliary space is O(n).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| points = 00 | 0 | A single point needs no connections. |
| points = 00 34 | 7 | Two points — the one Manhattan edge, |3|+|4| = 7. |
| points = 11 14 51 | 7 | An L of three points — the two legs (3 and 4) span them, skipping the long hypotenuse. |
| points = 00 20 50 90 | 9 | Collinear points — the MST chains the adjacent gaps 2+3+4. |
| points = 00 03 40 43 | 10 | A 4×3 rectangle — the MST uses three sides (3 + 4 + 3). |
Try it yourself
Write your solution against the real judge before checking the reference.