DSA-117 · FOCUSED PRACTICE
Minimum Cost to Connect Points
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 3346 deterministic checks. Learner drafts are not executed.
Understand the problem
Treat each input point as a distinct vertex. Any pair can be connected with an undirected edge costing their Manhattan distance. Return the minimum total edge cost needed to connect all points; empty and single-point inputs cost zero.
- points is a nonnull int[][] of nonnull coordinate pairs [x,y]. Null outer input throws NullPointerException; a null row or a row of any length other than two throws IllegalArgumentException before selection. At most 2,000 points is a size precondition for this dense implementation; all coordinates may span the full int domain.
- minimumCost returns long. Manhattan weight is abs((long)x1−x2)+abs((long)y1−y2), up to 8,589,934,590 per edge. The total can exceed int and remains within long under the point-count precondition. Distinct positions remain different vertices even when coordinates duplicate or row objects alias; a zero-cost edge can connect such vertices.
- Preserve source values and row identities, including shared row objects. No sorting or marking may alter the caller’s arrays. Auxiliary graph entries are privately allocated. Input must not be modified concurrently. The API returns the cost only, not a selected-edge list. It never materializes the complete graph in its main implementation and never sorts source rows.
Examples
Input:
[[0,0],[2,2],[3,10],[5,2],[7,0]]
Output:20One optimal tree uses edge costs 4,3,4,9. This is a sum of connecting edges, not a sum of distances from point zero.
Input:
[[1,1],[1,1],[2,1]]
Output:1Duplicate coordinates are distinct vertices connected at zero cost.
Input:
[[MIN,MIN],[MAX,MAX]]
Output:8589934590Both coordinate differences and their sum exceed int range.
Before you start
- Spanning trees, components, and safe crossing edges
- Distinguishing Prim connection keys from shortest-path distances
Recognize the structure
Every pair of points is a legal edge, so an explicit graph has Θ(n²) edges even though the input has only n coordinate pairs. The objective is total cost of a connected network. Because weights are nonnegative, cycles can be removed without increasing cost, so a spanning tree suffices. Dense Prim computes edge weights only when needed and keeps one cheapest connection key per outside vertex.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 162/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Why can an optimal connecting network be reduced to a spanning tree?
Hint 2
For each outside point, keep the cheapest edge into the growing tree.
Hint 3
Choose the minimum key, add it once, and update outside keys with one-edge Manhattan costs.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Kruskal with all pair edges
Generate each unordered pair once, compute its long Manhattan weight, sort all edges, then use disjoint-set membership to add an edge only when it joins different components. Stop after n−1 joins. This compiling baseline makes cycle avoidance explicit but allocates Θ(n²) edge records and pays for sorting. The main implementation avoids that complete edge list.
Improve the baseline
Represent a growing connected tree
Let used[v] mark vertices already selected. For every outside point, best[v] is the cheapest edge from a selected point, not the cost of a multi-edge path from the root. Seed best[0]=0 as a virtual root admission; all other keys start infinite. The complete graph guarantees a finite candidate after the root scan.
Scan for the smallest crossing key
At each iteration scan indices in ascending order and choose the unused vertex with the smallest best value. Strict comparison keeps the smallest index on ties. Mark it used and add its key to total. The first zero key admits the root but contributes no self-edge; each later admission corresponds to one real tree edge.
Update only with the newly admitted point
For each unused point compute its Manhattan distance to the new vertex. Replace its key if that single edge is cheaper. Do not add the new vertex’s own key: that would create shortest-path-style labels. After the scan, every outside key again summarizes the cheapest crossing edge from the whole current tree.
Why it is correct
Tree representation invariant
Initially the selected set contains one root and no real edges. Every subsequent admission connects one previously outside vertex by one edge to the selected set. Connectivity is maintained and no cycle is introduced. After n admissions, n−1 real edges form a spanning tree.
Cheapest cut edge is safe
For the cut between selected and unused vertices, the minimum best key is the lightest crossing edge. Take an optimal tree containing previously chosen edges. If it omits this crossing edge, insert it to form a cycle; that cycle contains another crossing edge of at least as much weight. Replacing that edge preserves a spanning tree, does not increase cost, and retains the selected edges. Thus the greedy addition is compatible with some optimum.
Key updates and completion
Before a new admission, best[v] is the minimum over edges from all previously selected vertices. Comparing the one newly available edge extends that minimum exactly. By induction each chosen edge is safe, and the final tree is optimal. Duplicate coordinates and equal weights do not affect the exchange inequality or connectivity argument.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
private static void validate(int[][] points) {
Objects.requireNonNull(points,"points");for(int[] point:points)if(point==null||point.length!=2)throw new IllegalArgumentException("invalid coordinate pair");
}
private static long weight(int[] a,int[] b) {return Math.abs((long)a[0]-b[0])+Math.abs((long)a[1]-b[1]);}
public static long minimumCost(int[][] points) {
validate(points);int n=points.length;if(n==0)return 0;
long[] best=new long[n];Arrays.fill(best,Long.MAX_VALUE);best[0]=0;boolean[] used=new boolean[n];long total=0;
for(int count=0;count<n;count++) {
int v=-1;for(int next=0;next<n;next++)if(!used[next]&&(v<0||best[next]<best[v]))v=next;
used[v]=true;total+=best[v];
for(int next=0;next<n;next++)if(!used[next]) {
long candidate=weight(points[v],points[next]);
if(candidate<best[next])best[next]=candidate;
}
}
return total;
}
private record Edge(int a,int b,long cost) {}
private static int root(int[] p,int v){while(p[v]!=v){p[v]=p[p[v]];v=p[v];}return v;}
public static long baseline(int[][] points) {
validate(points);List<Edge> edges=new ArrayList<>();int n=points.length;for(int a=0;a<n;a++)for(int b=a+1;b<n;b++)edges.add(new Edge(a,b,weight(points[a],points[b])));edges.sort(Comparator.comparingLong(Edge::cost));
int[] parent=new int[n],size=new int[n];for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}long total=0;int joined=0;for(Edge edge:edges){int a=root(parent,edge.a()),b=root(parent,edge.b());if(a!=b){if(size[a]<size[b]){int swap=a;a=b;b=swap;}parent[b]=a;size[a]+=size[b];total+=edge.cost();if(++joined==n-1)break;}}return total;
}
}
Read the meaningful blocks
A key is one connection edge
Prim stores the cost to attach an outside point to any selected point. Dijkstra would store an entire root-to-point route cost and relax with addition. These algorithms can have similar minimum-selection loops yet solve different optimization problems; their recurrence and proof must be stated separately.
Dense scanning avoids an unnecessary heap
With n² implicit candidate pairs, O(n) minimum scans across n selections match the O(n²) update work. A heap version can add logarithmic work and many proposals unless a more specialized geometric algorithm reduces candidate edges first. Two arrays plus on-demand distances suffice here.
Widen both coordinate differences safely
Each subtraction is explicitly long before abs. The two long absolute differences are summed into a long, and total is long as well. No square roots or squared Euclidean lengths belong in Manhattan distance. Source points remain read-only even when the same row appears twice.
Complexity
For n points, shape validation is O(n). The main method performs n minimum scans and at most n(n−1)/2 meaningful outside-key updates, giving O(n²+1) time and O(n+1) auxiliary storage. It stores no adjacency list or pair records. Output is one long; an optional future edge witness would require O(n) output storage.
The all-pairs Kruskal baseline builds M=n(n−1)/2 edge records and sorts them in O(M log(M+1)) time. Union by size with path halving adds amortized O(M α(n+1)) work; storage is O(M+n+1). Unlike the main method, it explicitly allocates quadratic pair records. Empty and singleton cases require only constant work beyond validation.
Exact-state walkthroughs
Reveal normal and boundary traces
Each outside key tracks the cheapest edge into the current tree
Input: [[0,0],[2,2],[3,10],[5,2],[7,0]] · Minimum spanning connection cost: 20
Step 1 of 18: Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
Phase: initial.
Selected points define one side of the cut. Each outside key is a single connection edge cost, measured in Manhattan units.
- point 0: (0, 0)outside the treeconnection key: 0 — virtual root zero
- point 1: (2, 2)outside the treeconnection key: ∞ (no finite label)
- point 2: (3, 10)outside the treeconnection key: ∞ (no finite label)
- point 3: (5, 2)outside the treeconnection key: ∞ (no finite label)
- point 4: (7, 0)outside the treeconnection key: ∞ (no finite label)
Admission history — point indices, not source-array reordering
Empty.
Accumulated tree cost: 0.
After a complete scan, every outside key is the cheapest edge into the selected set. Minimum selection uses ascending indices to break equal keys. No complete pair-edge list or returned edge witness is stored.
∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Every outside point gets a finite connection after the root scan. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.
| Variable | Value |
|---|---|
| input | [[0,0],[2,2],[3,10],[5,2],[7,0]] |
| best | [0,null,null,null,null] |
| used | [false,false,false,false,false] |
| selected | [] |
| total | 0 |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] points) { 4 Objects.requireNonNull(points,"points");for(int[] point:points)if(point==null||point.length!=2)throw new IllegalArgumentException("invalid coordinate pair"); 5 } 6 private static long weight(int[] a,int[] b) {return Math.abs((long)a[0]-b[0])+Math.abs((long)a[1]-b[1]);} 7 public static long minimumCost(int[][] points) { 8 validate(points);int n=points.length;if(n==0)return 0; 9 long[] best=new long[n];Arrays.fill(best,Long.MAX_VALUE);best[0]=0;boolean[] used=new boolean[n];long total=0; 10 for(int count=0;count<n;count++) { 11 int v=-1;for(int next=0;next<n;next++)if(!used[next]&&(v<0||best[next]<best[v]))v=next; 12 used[v]=true;total+=best[v]; 13 for(int next=0;next<n;next++)if(!used[next]) { 14 long candidate=weight(points[v],points[next]); 15 if(candidate<best[next])best[next]=candidate; 16 } 17 } 18 return total; 19 } 20 private record Edge(int a,int b,long cost) {} 21 private static int root(int[] p,int v){while(p[v]!=v){p[v]=p[p[v]];v=p[v];}return v;} 22 public static long baseline(int[][] points) { 23 validate(points);List<Edge> edges=new ArrayList<>();int n=points.length;for(int a=0;a<n;a++)for(int b=a+1;b<n;b++)edges.add(new Edge(a,b,weight(points[a],points[b])));edges.sort(Comparator.comparingLong(Edge::cost)); 24 int[] parent=new int[n],size=new int[n];for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}long total=0;int joined=0;for(Edge edge:edges){int a=root(parent,edge.a()),b=root(parent,edge.b());if(a!=b){if(size[a]<size[b]){int swap=a;a=b;b=swap;}parent[b]=a;size[a]+=size[b];total+=edge.cost();if(++joined==n-1)break;}}return total; 25 } 26 } 27
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,null,null,null,null]- used
[false,false,false,false,false]- selected
[]- total
0- phase
"initial"- current
null
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,null,null,null,null]- used
[true,false,false,false,false]- selected
[0]- total
0- phase
"select"- current
0- count
0
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,null,null,null]- used
[true,false,false,false,false]- selected
[0]- total
0- phase
"connect"- current
0- next
1- candidate
4- improved
true
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,13,null,null]- used
[true,false,false,false,false]- selected
[0]- total
0- phase
"connect"- current
0- next
2- candidate
13- improved
true
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,13,7,null]- used
[true,false,false,false,false]- selected
[0]- total
0- phase
"connect"- current
0- next
3- candidate
7- improved
true
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,13,7,7]- used
[true,false,false,false,false]- selected
[0]- total
0- phase
"connect"- current
0- next
4- candidate
7- improved
true
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,13,7,7]- used
[true,true,false,false,false]- selected
[0,1]- total
4- phase
"select"- current
1- count
1
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,7,7]- used
[true,true,false,false,false]- selected
[0,1]- total
4- phase
"connect"- current
1- next
2- candidate
9- improved
true
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,3,7]- used
[true,true,false,false,false]- selected
[0,1]- total
4- phase
"connect"- current
1- next
3- candidate
3- improved
true
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,3,7]- used
[true,true,false,false,false]- selected
[0,1]- total
4- phase
"connect"- current
1- next
4- candidate
7- improved
false
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,3,7]- used
[true,true,false,true,false]- selected
[0,1,3]- total
7- phase
"select"- current
3- count
2
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,3,7]- used
[true,true,false,true,false]- selected
[0,1,3]- total
7- phase
"connect"- current
3- next
2- candidate
10- improved
false
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,3,4]- used
[true,true,false,true,false]- selected
[0,1,3]- total
7- phase
"connect"- current
3- next
4- candidate
4- improved
true
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,3,4]- used
[true,true,false,true,true]- selected
[0,1,3,4]- total
11- phase
"select"- current
4- count
3
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,3,4]- used
[true,true,false,true,true]- selected
[0,1,3,4]- total
11- phase
"connect"- current
4- next
2- candidate
14- improved
false
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,3,4]- used
[true,true,true,true,true]- selected
[0,1,3,4,2]- total
20- phase
"select"- current
2- count
4
- Return the spanning-tree total.
Every nonroot selection adds one cheapest crossing edge. Equal or duplicate coordinates can add zero-cost edges; an empty or single-point input costs zero.
- input
[[0,0],[2,2],[3,10],[5,2],[7,0]]- best
[0,4,9,3,4]- used
[true,true,true,true,true]- selected
[0,1,3,4,2]- total
20- phase
"complete"- current
null
- Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
- result
20
Duplicate coordinates still represent separate vertices
Input: [[1,1],[1,1],[2,1]] · Minimum spanning connection cost: 1
Step 1 of 9: Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
Phase: initial.
Selected points define one side of the cut. Each outside key is a single connection edge cost, measured in Manhattan units.
- point 0: (1, 1)outside the treeconnection key: 0 — virtual root zero
- point 1: (1, 1)outside the treeconnection key: ∞ (no finite label)
- point 2: (2, 1)outside the treeconnection key: ∞ (no finite label)
Admission history — point indices, not source-array reordering
Empty.
Accumulated tree cost: 0.
After a complete scan, every outside key is the cheapest edge into the selected set. Minimum selection uses ascending indices to break equal keys. No complete pair-edge list or returned edge witness is stored.
∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Every outside point gets a finite connection after the root scan. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.
| Variable | Value |
|---|---|
| input | [[1,1],[1,1],[2,1]] |
| best | [0,null,null] |
| used | [false,false,false] |
| selected | [] |
| total | 0 |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] points) { 4 Objects.requireNonNull(points,"points");for(int[] point:points)if(point==null||point.length!=2)throw new IllegalArgumentException("invalid coordinate pair"); 5 } 6 private static long weight(int[] a,int[] b) {return Math.abs((long)a[0]-b[0])+Math.abs((long)a[1]-b[1]);} 7 public static long minimumCost(int[][] points) { 8 validate(points);int n=points.length;if(n==0)return 0; 9 long[] best=new long[n];Arrays.fill(best,Long.MAX_VALUE);best[0]=0;boolean[] used=new boolean[n];long total=0; 10 for(int count=0;count<n;count++) { 11 int v=-1;for(int next=0;next<n;next++)if(!used[next]&&(v<0||best[next]<best[v]))v=next; 12 used[v]=true;total+=best[v]; 13 for(int next=0;next<n;next++)if(!used[next]) { 14 long candidate=weight(points[v],points[next]); 15 if(candidate<best[next])best[next]=candidate; 16 } 17 } 18 return total; 19 } 20 private record Edge(int a,int b,long cost) {} 21 private static int root(int[] p,int v){while(p[v]!=v){p[v]=p[p[v]];v=p[v];}return v;} 22 public static long baseline(int[][] points) { 23 validate(points);List<Edge> edges=new ArrayList<>();int n=points.length;for(int a=0;a<n;a++)for(int b=a+1;b<n;b++)edges.add(new Edge(a,b,weight(points[a],points[b])));edges.sort(Comparator.comparingLong(Edge::cost)); 24 int[] parent=new int[n],size=new int[n];for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}long total=0;int joined=0;for(Edge edge:edges){int a=root(parent,edge.a()),b=root(parent,edge.b());if(a!=b){if(size[a]<size[b]){int swap=a;a=b;b=swap;}parent[b]=a;size[a]+=size[b];total+=edge.cost();if(++joined==n-1)break;}}return total; 25 } 26 } 27
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
- input
[[1,1],[1,1],[2,1]]- best
[0,null,null]- used
[false,false,false]- selected
[]- total
0- phase
"initial"- current
null
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[1,1],[1,1],[2,1]]- best
[0,null,null]- used
[true,false,false]- selected
[0]- total
0- phase
"select"- current
0- count
0
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[1,1],[1,1],[2,1]]- best
[0,0,null]- used
[true,false,false]- selected
[0]- total
0- phase
"connect"- current
0- next
1- candidate
0- improved
true
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[1,1],[1,1],[2,1]]- best
[0,0,1]- used
[true,false,false]- selected
[0]- total
0- phase
"connect"- current
0- next
2- candidate
1- improved
true
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[1,1],[1,1],[2,1]]- best
[0,0,1]- used
[true,true,false]- selected
[0,1]- total
0- phase
"select"- current
1- count
1
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[1,1],[1,1],[2,1]]- best
[0,0,1]- used
[true,true,false]- selected
[0,1]- total
0- phase
"connect"- current
1- next
2- candidate
1- improved
false
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[1,1],[1,1],[2,1]]- best
[0,0,1]- used
[true,true,true]- selected
[0,1,2]- total
1- phase
"select"- current
2- count
2
- Return the spanning-tree total.
Every nonroot selection adds one cheapest crossing edge. Equal or duplicate coordinates can add zero-cost edges; an empty or single-point input costs zero.
- input
[[1,1],[1,1],[2,1]]- best
[0,0,1]- used
[true,true,true]- selected
[0,1,2]- total
1- phase
"complete"- current
null
- Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
- result
1
Manhattan sum across both full-int coordinate ranges
Input: [[-2147483648,-2147483648],[2147483647,2147483647]] · Minimum spanning connection cost: 8589934590
Step 1 of 6: Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
Phase: initial.
Selected points define one side of the cut. Each outside key is a single connection edge cost, measured in Manhattan units.
- point 0: (MIN, MIN)outside the treeconnection key: 0 — virtual root zero
- point 1: (MAX, MAX)outside the treeconnection key: ∞ (no finite label)
Admission history — point indices, not source-array reordering
Empty.
Accumulated tree cost: 0.
After a complete scan, every outside key is the cheapest edge into the selected set. Minimum selection uses ascending indices to break equal keys. No complete pair-edge list or returned edge witness is stored.
∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Every outside point gets a finite connection after the root scan. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.
| Variable | Value |
|---|---|
| input | [[-2147483648,-2147483648],[2147483647,2147483647]] |
| best | [0,null] |
| used | [false,false] |
| selected | [] |
| total | 0 |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] points) { 4 Objects.requireNonNull(points,"points");for(int[] point:points)if(point==null||point.length!=2)throw new IllegalArgumentException("invalid coordinate pair"); 5 } 6 private static long weight(int[] a,int[] b) {return Math.abs((long)a[0]-b[0])+Math.abs((long)a[1]-b[1]);} 7 public static long minimumCost(int[][] points) { 8 validate(points);int n=points.length;if(n==0)return 0; 9 long[] best=new long[n];Arrays.fill(best,Long.MAX_VALUE);best[0]=0;boolean[] used=new boolean[n];long total=0; 10 for(int count=0;count<n;count++) { 11 int v=-1;for(int next=0;next<n;next++)if(!used[next]&&(v<0||best[next]<best[v]))v=next; 12 used[v]=true;total+=best[v]; 13 for(int next=0;next<n;next++)if(!used[next]) { 14 long candidate=weight(points[v],points[next]); 15 if(candidate<best[next])best[next]=candidate; 16 } 17 } 18 return total; 19 } 20 private record Edge(int a,int b,long cost) {} 21 private static int root(int[] p,int v){while(p[v]!=v){p[v]=p[p[v]];v=p[v];}return v;} 22 public static long baseline(int[][] points) { 23 validate(points);List<Edge> edges=new ArrayList<>();int n=points.length;for(int a=0;a<n;a++)for(int b=a+1;b<n;b++)edges.add(new Edge(a,b,weight(points[a],points[b])));edges.sort(Comparator.comparingLong(Edge::cost)); 24 int[] parent=new int[n],size=new int[n];for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}long total=0;int joined=0;for(Edge edge:edges){int a=root(parent,edge.a()),b=root(parent,edge.b());if(a!=b){if(size[a]<size[b]){int swap=a;a=b;b=swap;}parent[b]=a;size[a]+=size[b];total+=edge.cost();if(++joined==n-1)break;}}return total; 25 } 26 } 27
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
- input
[[-2147483648,-2147483648],[2147483647,2147483647]]- best
[0,null]- used
[false,false]- selected
[]- total
0- phase
"initial"- current
null
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[-2147483648,-2147483648],[2147483647,2147483647]]- best
[0,null]- used
[true,false]- selected
[0]- total
0- phase
"select"- current
0- count
0
- Consider the newly selected point as a connection for one outside point.
During this scan some outside keys still exclude the current point. After the scan each outside key is the cheapest edge from any selected point. Coordinate differences and their sum use long in Java.
- input
[[-2147483648,-2147483648],[2147483647,2147483647]]- best
[0,8589934590]- used
[true,false]- selected
[0]- total
0- phase
"connect"- current
0- next
1- candidate
8589934590- improved
true
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[-2147483648,-2147483648],[2147483647,2147483647]]- best
[0,8589934590]- used
[true,true]- selected
[0,1]- total
8589934590- phase
"select"- current
1- count
1
- Return the spanning-tree total.
Every nonroot selection adds one cheapest crossing edge. Equal or duplicate coordinates can add zero-cost edges; an empty or single-point input costs zero.
- input
[[-2147483648,-2147483648],[2147483647,2147483647]]- best
[0,8589934590]- used
[true,true]- selected
[0,1]- total
8589934590- phase
"complete"- current
null
- Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
- result
8589934590
Empty point set
Input: [] · Minimum spanning connection cost: 0
Step 1 of 3: Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
Phase: initial.
Selected points define one side of the cut. Each outside key is a single connection edge cost, measured in Manhattan units.
No points; no real edges are needed.
Admission history — point indices, not source-array reordering
Empty.
Accumulated tree cost: 0.
After a complete scan, every outside key is the cheapest edge into the selected set. Minimum selection uses ascending indices to break equal keys. No complete pair-edge list or returned edge witness is stored.
∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Every outside point gets a finite connection after the root scan. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.
| Variable | Value |
|---|---|
| input | [] |
| best | [] |
| used | [] |
| selected | [] |
| total | 0 |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] points) { 4 Objects.requireNonNull(points,"points");for(int[] point:points)if(point==null||point.length!=2)throw new IllegalArgumentException("invalid coordinate pair"); 5 } 6 private static long weight(int[] a,int[] b) {return Math.abs((long)a[0]-b[0])+Math.abs((long)a[1]-b[1]);} 7 public static long minimumCost(int[][] points) { 8 validate(points);int n=points.length;if(n==0)return 0; 9 long[] best=new long[n];Arrays.fill(best,Long.MAX_VALUE);best[0]=0;boolean[] used=new boolean[n];long total=0; 10 for(int count=0;count<n;count++) { 11 int v=-1;for(int next=0;next<n;next++)if(!used[next]&&(v<0||best[next]<best[v]))v=next; 12 used[v]=true;total+=best[v]; 13 for(int next=0;next<n;next++)if(!used[next]) { 14 long candidate=weight(points[v],points[next]); 15 if(candidate<best[next])best[next]=candidate; 16 } 17 } 18 return total; 19 } 20 private record Edge(int a,int b,long cost) {} 21 private static int root(int[] p,int v){while(p[v]!=v){p[v]=p[p[v]];v=p[v];}return v;} 22 public static long baseline(int[][] points) { 23 validate(points);List<Edge> edges=new ArrayList<>();int n=points.length;for(int a=0;a<n;a++)for(int b=a+1;b<n;b++)edges.add(new Edge(a,b,weight(points[a],points[b])));edges.sort(Comparator.comparingLong(Edge::cost)); 24 int[] parent=new int[n],size=new int[n];for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}long total=0;int joined=0;for(Edge edge:edges){int a=root(parent,edge.a()),b=root(parent,edge.b());if(a!=b){if(size[a]<size[b]){int swap=a;a=b;b=swap;}parent[b]=a;size[a]+=size[b];total+=edge.cost();if(++joined==n-1)break;}}return total; 25 } 26 } 27
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
- input
[]- best
[]- used
[]- selected
[]- total
0- phase
"initial"- current
null
- Return the spanning-tree total.
Every nonroot selection adds one cheapest crossing edge. Equal or duplicate coordinates can add zero-cost edges; an empty or single-point input costs zero.
- input
[]- best
[]- used
[]- selected
[]- total
0- phase
"complete"- current
null
- Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
- result
0
Single point virtual admission
Input: [[8,-3]] · Minimum spanning connection cost: 0
Step 1 of 4: Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
Phase: initial.
Selected points define one side of the cut. Each outside key is a single connection edge cost, measured in Manhattan units.
- point 0: (8, -3)outside the treeconnection key: 0 — virtual root zero
Admission history — point indices, not source-array reordering
Empty.
Accumulated tree cost: 0.
After a complete scan, every outside key is the cheapest edge into the selected set. Minimum selection uses ascending indices to break equal keys. No complete pair-edge list or returned edge witness is stored.
∞ is displayed as null in the exact state table and means Java Long.MAX_VALUE. Every outside point gets a finite connection after the root scan. Input values and row identities stay unchanged. Histories and logical frontier pictures are teaching views, excluded from Java workspace.
| Variable | Value |
|---|---|
| input | [[8,-3]] |
| best | [0] |
| used | [false] |
| selected | [] |
| total | 0 |
| phase | "initial" |
| current | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static void validate(int[][] points) { 4 Objects.requireNonNull(points,"points");for(int[] point:points)if(point==null||point.length!=2)throw new IllegalArgumentException("invalid coordinate pair"); 5 } 6 private static long weight(int[] a,int[] b) {return Math.abs((long)a[0]-b[0])+Math.abs((long)a[1]-b[1]);} 7 public static long minimumCost(int[][] points) { 8 validate(points);int n=points.length;if(n==0)return 0; 9 long[] best=new long[n];Arrays.fill(best,Long.MAX_VALUE);best[0]=0;boolean[] used=new boolean[n];long total=0; 10 for(int count=0;count<n;count++) { 11 int v=-1;for(int next=0;next<n;next++)if(!used[next]&&(v<0||best[next]<best[v]))v=next; 12 used[v]=true;total+=best[v]; 13 for(int next=0;next<n;next++)if(!used[next]) { 14 long candidate=weight(points[v],points[next]); 15 if(candidate<best[next])best[next]=candidate; 16 } 17 } 18 return total; 19 } 20 private record Edge(int a,int b,long cost) {} 21 private static int root(int[] p,int v){while(p[v]!=v){p[v]=p[p[v]];v=p[v];}return v;} 22 public static long baseline(int[][] points) { 23 validate(points);List<Edge> edges=new ArrayList<>();int n=points.length;for(int a=0;a<n;a++)for(int b=a+1;b<n;b++)edges.add(new Edge(a,b,weight(points[a],points[b])));edges.sort(Comparator.comparingLong(Edge::cost)); 24 int[] parent=new int[n],size=new int[n];for(int v=0;v<n;v++){parent[v]=v;size[v]=1;}long total=0;int joined=0;for(Edge edge:edges){int a=root(parent,edge.a()),b=root(parent,edge.b());if(a!=b){if(size[a]<size[b]){int swap=a;a=b;b=swap;}parent[b]=a;size[a]+=size[b];total+=edge.cost();if(++joined==n-1)break;}}return total; 25 } 26 } 27
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Seed point zero with a virtual cost-zero entry.
Points are indexed vertices even when coordinates coincide. No edge list is built. null denotes no known connection; the initial zero is not an actual self-edge.
- input
[[8,-3]]- best
[0]- used
[false]- selected
[]- total
0- phase
"initial"- current
null
- Take the least connection cost crossing the current cut.
Strict comparison during an ascending scan breaks equal costs by smallest index. These are edge keys, not source-to-point path sums. The root contributes zero.
- input
[[8,-3]]- best
[0]- used
[true]- selected
[0]- total
0- phase
"select"- current
0- count
0
- Return the spanning-tree total.
Every nonroot selection adds one cheapest crossing edge. Equal or duplicate coordinates can add zero-cost edges; an empty or single-point input costs zero.
- input
[[8,-3]]- best
[0]- used
[true]- selected
[0]- total
0- phase
"complete"- current
null
- Return the documented result without changing caller input.
Static states and logical pictures are teaching histories, excluded from Java workspace. The result uses long arithmetic; shown fixture numbers are exact within JavaScript’s safe integer range.
- result
0
Test the contract
Input:
Empty, one point, duplicate points
Output:0 or the necessary remaining connection costChecks the virtual root and distinct identities.
Input:
Five-point example
Output:20Separates a growing MST from a fixed root star.
Input:
Opposite full-int coordinates
Output:8589934590Tests both differences and sum.
Input:
All small labeled point sets
Output:minimum enumerated spanning-tree costThe independent Java oracle enumerates Prüfer-coded trees instead of implementing another greedy loop.
Input:
2,000 collinear points
Output:1999Exercises the intended dense bound with linear workspace.
Common mistakes and counterexamples
Add the selected key into every candidate
Counterexample: That computes a path-like cumulative quantity instead of a crossing edge cost.
Update best[next] with just weight(points[v],points[next]).
Connect every point directly to point zero
Counterexample: A star is connected but can be much more expensive than using intermediate connections.
Compare connections from every admitted point through the key invariant.
Collapse duplicate coordinate rows
Counterexample: They are distinct required vertices even when their cheapest connection is zero.
Use source indices as identities and permit zero-cost edges.
Use int Manhattan arithmetic
Counterexample: Two extreme points cost 8589934590.
Widen before both differences and keep weight and total as long.
Follow-ups
Return the actual network.
Keep a parent index when a key strictly improves. On each nonroot selection emit that parent edge into a fresh result list. Specify tie rules, verify acyclicity and connectivity, and separate O(n) witness output from auxiliary space.
Use a sparse supplied graph.
The complete-graph connectivity guarantee disappears. Detect an infinite minimum key and return a documented impossible outcome; use adjacency lists and a heap when scanning all possible pairs would be wasteful.
Handle far more points.
Research and prove a Manhattan-MST candidate-edge reduction before replacing the dense loop. Geometry-specific sweeps need careful coordinate transforms, duplicate handling, long arithmetic, and validation against small all-pairs optima; a heap alone does not remove quadratic pair work.
Related foundations
- Greedy reasoning: justify compressed choices
- Disjoint-set foundations: partitions, representatives, and ownership
- Heaps: retain the useful frontier