DSA-117 · Dense Prim over implicit Manhattan edges with the MST cut property

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: 20
One 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: 1
Duplicate coordinates are distinct vertices connected at zero cost.
Input: [[MIN,MIN],[MAX,MAX]]
Output: 8589934590
Both 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.

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.

Manhattan spanning tree — cheapest connections across a cut

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.

State after this step
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.

Manhattan spanning tree — cheapest connections across a cut

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.

State after this step
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.

Manhattan spanning tree — cheapest connections across a cut

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.

State after this step
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.

Manhattan spanning tree — cheapest connections across a cut

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.

State after this step
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.

Manhattan spanning tree — cheapest connections across a cut

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.

State after this step
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 cost
Checks the virtual root and distinct identities.
Input: Five-point example
Output: 20
Separates a growing MST from a fixed root star.
Input: Opposite full-int coordinates
Output: 8589934590
Tests both differences and sum.
Input: All small labeled point sets
Output: minimum enumerated spanning-tree cost
The independent Java oracle enumerates Prüfer-coded trees instead of implementing another greedy loop.
Input: 2,000 collinear points
Output: 1999
Exercises 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.

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.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 162/20,000 characters

Self-review

Can I prove the cut exchange and show that each admission adds exactly one real edge after the root?Can I distinguish connection keys from root shortest distances?Can I account for all-pairs baseline storage and its actual DSU implementation?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform parity claims.