DSA-071 · Exact squared-distance rank with a bounded max-heap

K Closest Points to Origin

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 4089 deterministic checks. Learner drafts are not executed.

Understand the problem

Return k closest input point occurrences to the origin, ordered by squared distance then original input index. Copy coordinates into fresh output rows and support the full int coordinate range exactly.

points is nonnull with at most 100,000 rows; each row must be nonnull and contain exactly two int coordinates. Invalid rows or k outside 0..n throw IllegalArgumentException; null top-level input throws NullPointerException. Rows are validated even when k=0.
Distance ties prefer the earlier input index; duplicate coordinate occurrences count separately. Return a fresh int[k][2], with distinct fresh row objects and no aliases to input rows. Source cells and row references remain unchanged; shared input rows are allowed.
Squared distance lies in [0,2^63]. Each square fits signed long, but their sum can equal 2^63 at (MIN,MIN). Java’s wrapped bit pattern is deliberately compared as unsigned with Long.compareUnsigned. Trace distances are exact decimal strings; neither floating square roots nor a signed-overflow ordering is used.

Examples

Input: [[1,3],[−2,2],[2,−2],[0,0]], k=2
Output: [[0,0],[−2,2]]
Origin wins. The distance-eight tie favors input index 1 over 2.
Input: [[MIN,MIN],[MAX,MAX],[MIN,MAX]], k=2
Output: [[MAX,MAX],[MIN,MAX]]
MIN/MIN has exact squared distance 9,223,372,036,854,775,808 and is farthest, despite its negative signed-long bit pattern.
Input: [[1,1]], k=0
Output: fresh []
Validation still checks row shape, while no point is selected.

Before you start

Heap retention versus output ordering
Widened products and signed versus unsigned long comparison

Recognize the structure

Square roots do not affect ordering. Selection needs the farthest retained occurrence at the root, and deterministic ties require keeping its original index. Numeric correctness is part of the algorithm: promoting the products alone does not make the sum fit signed long for every int pair.

Try before revealing

Hint 1

Squared distance has the same order as distance, but audit its maximum possible value.

Hint 2

Which retained point should be evicted when one more point arrives?

Hint 3

Use exact unsigned squared-distance/index rank, a worst-first heap, and fresh sorted output rows.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Sort all indexed points by exact distance

Build indexed point records and sort by unsigned squared distance then ascending input index; copy the first k into new rows. For [[1,3],[−2,2],[2,−2],[0,0]], full index order is [3,1,2,0]. Time O(n log(n+1)), O(n) selection records plus O(k) output. Tests use BigInteger distances as an independent oracle, rather than reusing the unsigned comparator.

Improve the baseline

Represent the complete distance domain

Each coordinate square is at most 2^62. Their sum is at most 2^63, fitting a 64-bit unsigned bit pattern. Widen each coordinate before multiplication, allow the defined long addition wrap, and compare the result using Long.compareUnsigned.

Retain the best k occurrences

BEST compares unsigned distance then source index. A queue with BEST.reversed() exposes greatest distance and latest index first. Offer points in input order and poll one worst entry on overflow.

Sort and copy only selected coordinates

Sort retained records by BEST and allocate a new two-int row per output occurrence. A duplicate point must still receive its own output row; selecting references to source rows would violate ownership.

Why it is correct

Distance rank is exact

The arithmetic computes each exact nonnegative distance modulo 2^64. Since the true range ends at 2^63, no two different distances collide modulo 2^64; unsigned comparison is therefore identical to mathematical distance comparison. Index ties make the rank total.

Heap invariant

After each processed point, the heap contains the best min(k,processed) input occurrences. The worst-first root removes precisely the rank outside the best k after an insertion, including equal-distance index ties.

Output ownership and order

All occurrences are considered once. Sorting the selected records gives increasing distance/index rank, and writing their copied x/y fields into newly allocated distinct rows preserves source data and prevents output/input aliases.

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.ArrayList;
import java.util.Comparator;
import java.util.Objects;
import java.util.PriorityQueue;
public final class Solution {
    private record Point(int index, int x, int y, long squared) {}
    private static final Comparator<Point> BEST = (a,b) -> {
        int distance = Long.compareUnsigned(a.squared, b.squared);
        return distance != 0 ? distance : Integer.compare(a.index, b.index);
    };
    private static void validate(int[][] points, int k) {
        Objects.requireNonNull(points, "points");
        if (k < 0 || k > points.length) throw new IllegalArgumentException("invalid k");
        for (int[] row : points) if (row == null || row.length != 2) throw new IllegalArgumentException("point needs two coordinates");
    }
    private static Point point(int[] row, int index) {
        long squared = (long) row[0] * row[0] + (long) row[1] * row[1];
        return new Point(index, row[0], row[1], squared);
    }
    private static int[][] output(ArrayList<Point> ordered) {
        ordered.sort(BEST);
        int[][] result = new int[ordered.size()][2];
        for (int i = 0; i < ordered.size(); i++) {
            result[i][0] = ordered.get(i).x;
            result[i][1] = ordered.get(i).y;
        }
        return result;
    }
    public static int[][] closest(int[][] points, int k) {
        validate(points, k);
        PriorityQueue<Point> selected = new PriorityQueue<>(BEST.reversed());
        for (int i = 0; i < points.length; i++) {
            selected.offer(point(points[i], i));
            if (selected.size() > k) selected.poll();
        }
        return output(new ArrayList<>(selected));
    }
    public static int[][] baseline(int[][] points, int k) {
        validate(points, k);
        ArrayList<Point> ordered = new ArrayList<>();
        for (int i = 0; i < points.length; i++) ordered.add(point(points[i],i));
        ordered.sort(BEST);
        return output(new ArrayList<>(ordered.subList(0,k)));
    }
}

Read the meaningful blocks

Validate structural rows

Each row must have exactly two entries; the loop validates before selection, even for k=0.

Unsigned comparison is intentional

Long.compareUnsigned handles the single signed-boundary case that ordinary Long.compare would misorder. Do not replace it with subtraction or Math.addExact, which would reject the valid MIN/MIN point.

Allocate result rows

new int[ordered.size()][2] creates independent rows even when source occurrences share one row object or have equal coordinates.

Complexity

Bounded selection and ordered output take O(n log(k+2)+k log(k+2)) time, including O(n) validation. Peak selection workspace is O(k+1), excluding O(k) fresh returned rows. New candidate records are allocated over time, but only O(k+1) are retained at once.

The baseline uses O(n log(n+1)) time and O(n) auxiliary records. Quickselect can improve expected membership selection time, but deterministic ordered output still requires sorting k chosen records and a worst-case guarantee needs a different selection strategy.

Exact-state walkthroughs

Reveal normal and boundary traces

Origin and equal-distance index ties

Input: {"points":[[1,3],[-2,2],[2,-2],[0,0]],"k":2} · Result: [[0,0],[-2,2]]

Step 1 of 7: Validate coordinates and start an empty worst-first frontier.

Distances are exact decimal strings, including 2^63. Java compares the corresponding long bit patterns as unsigned.

Closest points — exact distance strings and occurrence rank

k=2. Points processed: 0. Equal distances prefer earlier source indices.

Original points — exact squared distance

source 0: (1, 3); d²=10
source 1: (-2, 2); d²=8
source 2: (2, -2); d²=8
source 3: (0, 0); d²=0

Retained source occurrences — farthest/latest first

Empty.

Distances may reach 2^63. Java compares unsigned long bit patterns; the display uses decimal strings. Returned rows are fresh copies.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
points	`[{"index":0,"x":1,"y":3,"squared":"10"},{"index":1,"x":-2,"y":2,"squared":"8"},{"index":2,"x":2,"y":-2,"squared":"8"},{"index":3,"x":0,"y":0,"squared":"0"}]`
k	`2`
heap	`[]`
phase	`"initial"`
processed	`0`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     private record Point(int index, int x, int y, long squared) {}
 7     private static final Comparator<Point> BEST = (a,b) -> {
 8         int distance = Long.compareUnsigned(a.squared, b.squared);
 9         return distance != 0 ? distance : Integer.compare(a.index, b.index);
10     };
11     private static void validate(int[][] points, int k) {
12         Objects.requireNonNull(points, "points");
13         if (k < 0 || k > points.length) throw new IllegalArgumentException("invalid k");
14         for (int[] row : points) if (row == null || row.length != 2) throw new IllegalArgumentException("point needs two coordinates");
15     }
16     private static Point point(int[] row, int index) {
17         long squared = (long) row[0] * row[0] + (long) row[1] * row[1];
18         return new Point(index, row[0], row[1], squared);
19     }
20     private static int[][] output(ArrayList<Point> ordered) {
21         ordered.sort(BEST);
22         int[][] result = new int[ordered.size()][2];
23         for (int i = 0; i < ordered.size(); i++) {
24             result[i][0] = ordered.get(i).x;
25             result[i][1] = ordered.get(i).y;
26         }
27         return result;
28     }
29     public static int[][] closest(int[][] points, int k) {
30         validate(points, k);
31         PriorityQueue<Point> selected = new PriorityQueue<>(BEST.reversed());
32         for (int i = 0; i < points.length; i++) {
33             selected.offer(point(points[i], i));
34             if (selected.size() > k) selected.poll();
35         }
36         return output(new ArrayList<>(selected));
37     }
38     public static int[][] baseline(int[][] points, int k) {
39         validate(points, k);
40         ArrayList<Point> ordered = new ArrayList<>();
41         for (int i = 0; i < points.length; i++) ordered.add(point(points[i],i));
42         ordered.sort(BEST);
43         return output(new ArrayList<>(ordered.subList(0,k)));
44     }
45 }
46

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate coordinates and start an empty worst-first frontier.
Distances are exact decimal strings, including 2^63. Java compares the corresponding long bit patterns as unsigned.
points
[{"index":0,"x":1,"y":3,"squared":"10"},{"index":1,"x":-2,"y":2,"squared":"8"},{"index":2,"x":2,"y":-2,"squared":"8"},{"index":3,"x":0,"y":0,"squared":"0"}]
k
2
heap
[]
phase
"initial"
processed
0
Retain the nearest occurrences, evicting farthest/latest ties.
The heap display is priority-sorted worst to best. Input point rows are untouched; membership ties use source index.
points
[{"index":0,"x":1,"y":3,"squared":"10"},{"index":1,"x":-2,"y":2,"squared":"8"},{"index":2,"x":2,"y":-2,"squared":"8"},{"index":3,"x":0,"y":0,"squared":"0"}]
k
2
heap
[{"index":0,"x":1,"y":3,"squared":"10"}]
phase
"select"
processed
1
current
0
candidate
{"index":0,"x":1,"y":3,"squared":"10"}
discarded
null
Retain the nearest occurrences, evicting farthest/latest ties.
The heap display is priority-sorted worst to best. Input point rows are untouched; membership ties use source index.
points
[{"index":0,"x":1,"y":3,"squared":"10"},{"index":1,"x":-2,"y":2,"squared":"8"},{"index":2,"x":2,"y":-2,"squared":"8"},{"index":3,"x":0,"y":0,"squared":"0"}]
k
2
heap
[{"index":0,"x":1,"y":3,"squared":"10"},{"index":1,"x":-2,"y":2,"squared":"8"}]
phase
"select"
processed
2
current
1
candidate
{"index":1,"x":-2,"y":2,"squared":"8"}
discarded
null
Retain the nearest occurrences, evicting farthest/latest ties.
The heap display is priority-sorted worst to best. Input point rows are untouched; membership ties use source index.
points
[{"index":0,"x":1,"y":3,"squared":"10"},{"index":1,"x":-2,"y":2,"squared":"8"},{"index":2,"x":2,"y":-2,"squared":"8"},{"index":3,"x":0,"y":0,"squared":"0"}]
k
2
heap
[{"index":2,"x":2,"y":-2,"squared":"8"},{"index":1,"x":-2,"y":2,"squared":"8"}]
phase
"select"
processed
3
current
2
candidate
{"index":2,"x":2,"y":-2,"squared":"8"}
discarded
{"index":0,"x":1,"y":3,"squared":"10"}
Retain the nearest occurrences, evicting farthest/latest ties.
The heap display is priority-sorted worst to best. Input point rows are untouched; membership ties use source index.
points
[{"index":0,"x":1,"y":3,"squared":"10"},{"index":1,"x":-2,"y":2,"squared":"8"},{"index":2,"x":2,"y":-2,"squared":"8"},{"index":3,"x":0,"y":0,"squared":"0"}]
k
2
heap
[{"index":1,"x":-2,"y":2,"squared":"8"},{"index":3,"x":0,"y":0,"squared":"0"}]
phase
"select"
processed
4
current
3
candidate
{"index":3,"x":0,"y":0,"squared":"0"}
discarded
{"index":2,"x":2,"y":-2,"squared":"8"}
Copy the selected coordinates into independent ranked rows.
Each output row is newly allocated in the Java implementation, even for duplicate or aliased input occurrences.
points
[{"index":0,"x":1,"y":3,"squared":"10"},{"index":1,"x":-2,"y":2,"squared":"8"},{"index":2,"x":2,"y":-2,"squared":"8"},{"index":3,"x":0,"y":0,"squared":"0"}]
k
2
heap
[{"index":1,"x":-2,"y":2,"squared":"8"},{"index":3,"x":0,"y":0,"squared":"0"}]
phase
"ordered"
processed
4
ordered
[{"index":3,"x":0,"y":0,"squared":"0"},{"index":1,"x":-2,"y":2,"squared":"8"}]
outputSources
[3,1]
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
[[0,0],[-2,2]]

Full int coordinates cross the signed long boundary

Input: {"points":[[-2147483648,-2147483648],[2147483647,2147483647],[-2147483648,2147483647]],"k":2} · Result: [[2147483647,2147483647],[-2147483648,2147483647]]

Step 1 of 6: Validate coordinates and start an empty worst-first frontier.

Distances are exact decimal strings, including 2^63. Java compares the corresponding long bit patterns as unsigned.

Closest points — exact distance strings and occurrence rank

k=2. Points processed: 0. Equal distances prefer earlier source indices.

Original points — exact squared distance

source 0: (-2147483648, -2147483648); d²=9223372036854775808
source 1: (2147483647, 2147483647); d²=9223372028264841218
source 2: (-2147483648, 2147483647); d²=9223372032559808513

Retained source occurrences — farthest/latest first

Empty.

Distances may reach 2^63. Java compares unsigned long bit patterns; the display uses decimal strings. Returned rows are fresh copies.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
points	`[{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"},{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"},{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"}]`
k	`2`
heap	`[]`
phase	`"initial"`
processed	`0`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     private record Point(int index, int x, int y, long squared) {}
 7     private static final Comparator<Point> BEST = (a,b) -> {
 8         int distance = Long.compareUnsigned(a.squared, b.squared);
 9         return distance != 0 ? distance : Integer.compare(a.index, b.index);
10     };
11     private static void validate(int[][] points, int k) {
12         Objects.requireNonNull(points, "points");
13         if (k < 0 || k > points.length) throw new IllegalArgumentException("invalid k");
14         for (int[] row : points) if (row == null || row.length != 2) throw new IllegalArgumentException("point needs two coordinates");
15     }
16     private static Point point(int[] row, int index) {
17         long squared = (long) row[0] * row[0] + (long) row[1] * row[1];
18         return new Point(index, row[0], row[1], squared);
19     }
20     private static int[][] output(ArrayList<Point> ordered) {
21         ordered.sort(BEST);
22         int[][] result = new int[ordered.size()][2];
23         for (int i = 0; i < ordered.size(); i++) {
24             result[i][0] = ordered.get(i).x;
25             result[i][1] = ordered.get(i).y;
26         }
27         return result;
28     }
29     public static int[][] closest(int[][] points, int k) {
30         validate(points, k);
31         PriorityQueue<Point> selected = new PriorityQueue<>(BEST.reversed());
32         for (int i = 0; i < points.length; i++) {
33             selected.offer(point(points[i], i));
34             if (selected.size() > k) selected.poll();
35         }
36         return output(new ArrayList<>(selected));
37     }
38     public static int[][] baseline(int[][] points, int k) {
39         validate(points, k);
40         ArrayList<Point> ordered = new ArrayList<>();
41         for (int i = 0; i < points.length; i++) ordered.add(point(points[i],i));
42         ordered.sort(BEST);
43         return output(new ArrayList<>(ordered.subList(0,k)));
44     }
45 }
46

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate coordinates and start an empty worst-first frontier.
Distances are exact decimal strings, including 2^63. Java compares the corresponding long bit patterns as unsigned.
points
[{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"},{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"},{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"}]
k
2
heap
[]
phase
"initial"
processed
0
Retain the nearest occurrences, evicting farthest/latest ties.
The heap display is priority-sorted worst to best. Input point rows are untouched; membership ties use source index.
points
[{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"},{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"},{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"}]
k
2
heap
[{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"}]
phase
"select"
processed
1
current
0
candidate
{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"}
discarded
null
Retain the nearest occurrences, evicting farthest/latest ties.
The heap display is priority-sorted worst to best. Input point rows are untouched; membership ties use source index.
points
[{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"},{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"},{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"}]
k
2
heap
[{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"},{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"}]
phase
"select"
processed
2
current
1
candidate
{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"}
discarded
null
Retain the nearest occurrences, evicting farthest/latest ties.
The heap display is priority-sorted worst to best. Input point rows are untouched; membership ties use source index.
points
[{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"},{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"},{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"}]
k
2
heap
[{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"},{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"}]
phase
"select"
processed
3
current
2
candidate
{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"}
discarded
{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"}
Copy the selected coordinates into independent ranked rows.
Each output row is newly allocated in the Java implementation, even for duplicate or aliased input occurrences.
points
[{"index":0,"x":-2147483648,"y":-2147483648,"squared":"9223372036854775808"},{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"},{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"}]
k
2
heap
[{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"},{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"}]
phase
"ordered"
processed
3
ordered
[{"index":1,"x":2147483647,"y":2147483647,"squared":"9223372028264841218"},{"index":2,"x":-2147483648,"y":2147483647,"squared":"9223372032559808513"}]
outputSources
[1,2]
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
[[2147483647,2147483647],[-2147483648,2147483647]]

Zero selected points

Input: {"points":[[1,1]],"k":0} · Result: []

Step 1 of 4: Validate coordinates and start an empty worst-first frontier.

Distances are exact decimal strings, including 2^63. Java compares the corresponding long bit patterns as unsigned.

Closest points — exact distance strings and occurrence rank

k=0. Points processed: 0. Equal distances prefer earlier source indices.

Original points — exact squared distance

source 0: (1, 1); d²=2

Retained source occurrences — farthest/latest first

Empty.

Distances may reach 2^63. Java compares unsigned long bit patterns; the display uses decimal strings. Returned rows are fresh copies.

Queue contents are sorted by logical priority for display. This is not Java PriorityQueue internal storage or iterator order.

State after this step
Variable	Value
points	`[{"index":0,"x":1,"y":1,"squared":"2"}]`
k	`0`
heap	`[]`
phase	`"initial"`
processed	`0`

See the affected Java block

 1 import java.util.ArrayList;
 2 import java.util.Comparator;
 3 import java.util.Objects;
 4 import java.util.PriorityQueue;
 5 public final class Solution {
 6     private record Point(int index, int x, int y, long squared) {}
 7     private static final Comparator<Point> BEST = (a,b) -> {
 8         int distance = Long.compareUnsigned(a.squared, b.squared);
 9         return distance != 0 ? distance : Integer.compare(a.index, b.index);
10     };
11     private static void validate(int[][] points, int k) {
12         Objects.requireNonNull(points, "points");
13         if (k < 0 || k > points.length) throw new IllegalArgumentException("invalid k");
14         for (int[] row : points) if (row == null || row.length != 2) throw new IllegalArgumentException("point needs two coordinates");
15     }
16     private static Point point(int[] row, int index) {
17         long squared = (long) row[0] * row[0] + (long) row[1] * row[1];
18         return new Point(index, row[0], row[1], squared);
19     }
20     private static int[][] output(ArrayList<Point> ordered) {
21         ordered.sort(BEST);
22         int[][] result = new int[ordered.size()][2];
23         for (int i = 0; i < ordered.size(); i++) {
24             result[i][0] = ordered.get(i).x;
25             result[i][1] = ordered.get(i).y;
26         }
27         return result;
28     }
29     public static int[][] closest(int[][] points, int k) {
30         validate(points, k);
31         PriorityQueue<Point> selected = new PriorityQueue<>(BEST.reversed());
32         for (int i = 0; i < points.length; i++) {
33             selected.offer(point(points[i], i));
34             if (selected.size() > k) selected.poll();
35         }
36         return output(new ArrayList<>(selected));
37     }
38     public static int[][] baseline(int[][] points, int k) {
39         validate(points, k);
40         ArrayList<Point> ordered = new ArrayList<>();
41         for (int i = 0; i < points.length; i++) ordered.add(point(points[i],i));
42         ordered.sort(BEST);
43         return output(new ArrayList<>(ordered.subList(0,k)));
44     }
45 }
46

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Validate coordinates and start an empty worst-first frontier.
Distances are exact decimal strings, including 2^63. Java compares the corresponding long bit patterns as unsigned.
points
[{"index":0,"x":1,"y":1,"squared":"2"}]
k
0
heap
[]
phase
"initial"
processed
0
Retain the nearest occurrences, evicting farthest/latest ties.
The heap display is priority-sorted worst to best. Input point rows are untouched; membership ties use source index.
points
[{"index":0,"x":1,"y":1,"squared":"2"}]
k
0
heap
[]
phase
"select"
processed
1
current
0
candidate
{"index":0,"x":1,"y":1,"squared":"2"}
discarded
{"index":0,"x":1,"y":1,"squared":"2"}
Copy the selected coordinates into independent ranked rows.
Each output row is newly allocated in the Java implementation, even for duplicate or aliased input occurrences.
points
[{"index":0,"x":1,"y":1,"squared":"2"}]
k
0
heap
[]
phase
"ordered"
processed
1
ordered
[]
outputSources
[]
Return the declared selection, identity view, operation outcomes, range, or minimum length.
Heap displays are priority-sorted logical state, not implementation storage. History shown in traces is excluded from Java auxiliary-space claims.
result
[]

Test the contract

Input: [],k=0
Output: fresh []
Empty valid input.
Input: Origin plus equal-distance points
Output: Origin, then earliest tied occurrence
Tie policy.
Input: (MIN,MIN) versus (MAX,MAX)
Output: MAX/MAX is closer
Unsigned-boundary arithmetic.
Input: Aliased input rows
Output: Distinct fresh output rows
Ownership independent of input aliases.
Input: Null/wrong-length row with k=0
Output: IllegalArgumentException
Validation cannot be skipped.

Common mistakes and counterexamples

Compute x*x in int first

Counterexample: For x=50,000, the product already overflows before assignment to long.

Cast an operand to long before each multiplication.

Assume two widened squares always fit signed long

Counterexample: (MIN,MIN) sums to 2^63 and looks negative as a signed long.

Use the stated unsigned representation or an arbitrary-precision alternative; tests compare against BigInteger.

Poll the closest retained point

Counterexample: A min-heap loses the best candidate on overflow.

Reverse the full distance/index rank so the root is farthest/worst.

Return input row references

Counterexample: Changing result[0][0] would change the caller’s data.

Allocate fresh rows and verify no input or sibling-row aliases.

Follow-ups

Use an arbitrary reference point.

Coordinate differences can exceed int and their squares can exceed signed/unsigned 64-bit range when the reference is also an arbitrary int point. Recalculate bounds and use BigInteger or a justified wider representation; do not reuse the origin proof blindly.

Return only unordered membership.

The heap already identifies the selected set; omit final rank sorting if the contract allows arbitrary order. Input-index ties at the membership boundary must still be honored if retained.

Apply quickselect.

Partition indexed records by the same exact total rank, choose k, then sort the selected prefix if ordered output is required. A copied work array is necessary to preserve the input.

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 · 131/20,000 characters

Self-review

I bound the sum, not only each product.My comparator preserves exact unsigned distance and input-index ties.I verify sorted coordinates, occurrence count, and row independence.

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

Related foundations

Heaps: retain the useful frontier

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-difficulty claims.