K Closest Points to Origin
Problem
points is a 2-D point [x, y]. Return the
k points with the smallest Euclidean distance to (0, 0), in any order.
The set of answers is guaranteed to be unique.[[1,3],[-2,2]], k=1Output[[-2,2]][[3,3],[5,-1],[-2,4]], k=2Output[[3,3],[-2,4]]1 ≤ k ≤ n ≤ 104 · -104 ≤ x, y ≤ 104
Try it yourself
class Solution {
public int[][] kClosest(int[][] points, int k) {
}
}
x² + y² (no
sqrt, same order). And you never need the k points sorted — only
separated from the rest, which is exactly what one partition step does.Instinct "K largest / smallest / closest / most frequent", or "always take the best available next"? Keep a heap - size k for top-K, or a ready-queue for scheduling.
Memory hack Guard the top-K club with a bouncer - a min-heap of size k whose root is the weakest member; anyone stronger kicks them out.
Open the Heap & Top-K guide →Approaches
Brute ForceSort All by Distance
O(n log n)Space O(log n) sort stackSort every point by squared distance and return the first k.
Fully orders all n points even though only the first k matter.
public int[][] kClosest(int[][] points, int k) { Arrays.sort(points, (a, b) -> Integer.compare(a[0] * a[0] + a[1] * a[1], b[0] * b[0] + b[1] * b[1])); return Arrays.copyOf(points, k); }
One-liner and correct, but sorts far more than required.
BetterMax-Heap of Size k
O(n log k)Space O(k)Keep the k closest points seen so far in a max-heap by distance. The root is the farthest of them; when the heap exceeds k, evict it. Every point that survives is closer than everything evicted.
public int[][] kClosest(int[][] points, int k) { PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> Integer.compare(dist(b), dist(a))); for (int[] p : points) { maxHeap.offer(p); if (maxHeap.size() > k) maxHeap.poll(); // drop the farthest } return maxHeap.toArray(new int[k][]); } private int dist(int[] p) { return p[0] * p[0] + p[1] * p[1]; }
Great for streams / huge n with small k; still a log factor.
OptimalQuickselect (Random Pivot)
O(n) avg, O(n²) worstSpace O(1)Partition around a random pivot's distance: closer points go left, the pivot
lands at its final index p. If p == k-1 the first k slots
are the answer; otherwise recurse (iteratively) into only the side containing
k-1. Expected work n + n/2 + n/4 + … = O(n).
public int[][] kClosest(int[][] points, int k) { Random rnd = new Random(); int lo = 0, hi = points.length - 1; while (lo < hi) { int p = partition(points, lo, hi, lo + rnd.nextInt(hi - lo + 1)); if (p == k - 1) break; if (p < k - 1) lo = p + 1; else hi = p - 1; } return Arrays.copyOf(points, k); } private int partition(int[][] pts, int lo, int hi, int pivotIdx) { swap(pts, pivotIdx, hi); int pivot = dist(pts[hi]), store = lo; for (int i = lo; i < hi; i++) { if (dist(pts[i]) < pivot) swap(pts, store++, i); } swap(pts, store, hi); // pivot to its final place return store; } private int dist(int[] p) { return p[0] * p[0] + p[1] * p[1]; } private void swap(int[][] a, int i, int j) { int[] t = a[i]; a[i] = a[j]; a[j] = t; }
Linear on average and in-place; random pivot makes the worst case unlikely.
int;
with larger coordinates switch to long.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Sort All by Distance | O(n log n) | O(log n) sort stack |
| Better | Max-Heap of Size k | O(n log k) | O(k) |
| Optimal | Quickselect (Random Pivot) | O(n) avg, O(n²) worst | O(1) |
- Using a min-heap of size k — it evicts the closest points instead of the farthest.
Math.sqrton doubles — slower and invites precision bugs; squares suffice.- Quickselect with a fixed pivot — O(n²) on sorted/adversarial input.
- Ask whether output order matters — if not, you don't need to sort.
- Contrast heap (streaming, O(k) memory) vs quickselect (in-place, needs all data).
- Explain quickselect's expected O(n) via the halving geometric series.