K Closest Points to Origin
You are given an array pointspoints[i] = [x, y]kk(0, 0)
Limits: 1 <= k <= points.length <= 10^4-10^4 <= x, y <= 10^4
The page gives two solutions.
Example 1
Output: [[-2, 2]]
Example 2
Output: [[3, 3], [-2, 4]]
How to Think About It
Step 1: Compare squared distances
The distance of (x, y)sqrt(x*x + y*y)x*x + y*y[-2, 2]
With coordinates up to 10^4 in size, the largest squared distance is 2 × 10^8. That fits in an int
Step 2: Sorting works but does extra work
Sort all points by squared distance and take the first k. This costs O(n log n), and it puts every point in order even though we only need to know which k come first.
Step 3: Keep only k candidates
Scan the points and keep the k closest seen so far. When a new point arrives, the one to compare with is the farthest of the kept points. If the new point is closer, the farthest one leaves.
A max-heap by distance keeps that farthest point on top, so each step costs O(log k). This is the same keep-k idea as
Step 4: The order inside the answer does not matter
The output can be in any order, so we only need to split the points into "k closest" and "the rest". Quickselect does exactly that split. It partitions around a pivot distance and then continues on the one side that holds position k - 1. On average each round halves the range, giving O(n).
Walkthrough
Solution 1 on Example 2 with k = 2[3, 3][5, -1][-2, 4]
| Point added | Squared distance | Heap size after offer | Polled (farthest) | Heap after (distances) |
|---|---|---|---|---|
| [3, 3] | 18 | 1 | nothing | {18} |
| [5, -1] | 26 | 2 | nothing | {26, 18}, top 26 |
| [-2, 4] | 20 | 3 | [5, -1] (26) | {20, 18}, top 20 |
The heap ends with [3, 3][-2, 4]
Solution 1: Max-Heap of Size k
kClosest
- The comparator:
reverses the natural order, so the farthest kept point sits on top and is the oneInteger.compare(dist(b), dist(a)) removes.poll - The size rule: after each
, a heap of k + 1 points loses its farthest one. The k points left are always the k closest of those seen so far.offer - Building the result:
returns the kept points in heap order, which is allowed because any order is accepted.heap.toArray(new int[0][]) - k equal to n: nothing is ever polled, and every point is returned. With
and[[0, 1], [1, 0]] both points come back.k = 2
A common mistake is to use the default PriorityQueuepoll[[-2, 4], [5, -1]]
import java.util.PriorityQueue;
public class KClosestPointsToOrigin {
public int[][] kClosest(int[][] points, int k) {
// max-heap by distance: the top is the farthest of the points kept so far
PriorityQueue<int[]> heap =
new PriorityQueue<>((a, b) -> Integer.compare(dist(b), dist(a)));
for (int[] p : points) {
heap.offer(p);
if (heap.size() > k) heap.poll(); // drop the farthest of the k + 1
}
return heap.toArray(new int[0][]);
}
private static int dist(int[] p) {
return p[0] * p[0] + p[1] * p[1]; // squared distance keeps the order, no sqrt needed
}
}
Solution 2: Quickselect
This version rearranges points
- Three-way partition: one pass over
leaves points closer than the pivot in[lo, hi] , points at the same distance in[lo, lt) , and farther points in[lt, gt] .(gt, hi] - Choosing a side: if index
is left ofk - 1 , the search continues in the closer part. If it is right oflt , it continues in the farther part. Otherwise index k - 1 holds a pivot-distance point and the front k are the answer.gt - Why ties are safe: the answer is unique, so the k-th and (k + 1)-th closest distances differ. Any points tied with the pivot inside the first k all belong in the answer.
- The random pivot: it makes a bad split on every round very unlikely, whatever order the input arrives in.
A common mistake is to always use the last element of the range as the pivot. If the points are already sorted by distance, such as [i, 0]k = 1
import java.util.Arrays;
import java.util.Random;
public class KClosestPointsQuickselect {
private final Random random = new Random();
public int[][] kClosest(int[][] points, int k) {
int lo = 0, hi = points.length - 1;
while (true) {
int pivot = dist(points[lo + random.nextInt(hi - lo + 1)]);
// after the loop: [lo, lt) closer, [lt, gt] same distance, (gt, hi] farther
int lt = lo, i = lo, gt = hi;
while (i <= gt) {
int d = dist(points[i]);
if (d < pivot) swap(points, lt++, i++);
else if (d > pivot) swap(points, i, gt--);
else i++;
}
if (k - 1 < lt) hi = lt - 1; // the k-th closest is in the closer part
else if (k - 1 > gt) lo = gt + 1; // it is in the farther part
else return Arrays.copyOf(points, k); // it has the pivot's distance: done
}
}
private static int dist(int[] p) {
return p[0] * p[0] + p[1] * p[1];
}
private static void swap(int[][] a, int i, int j) {
int[] t = a[i];
a[i] = a[j];
a[j] = t;
}
}
Complexity
- Solution 1 time: O(n log k). Each of the n points causes one
and at most oneoffer , and both cost O(log k) because the heap never holds more than k + 1 points.poll - Solution 1 space: O(k) for the heap and the returned array. Points that lose their place are dropped right away, so memory does not grow with n.
- Solution 2 time: O(n) on average, O(n²) in the worst case. Each round scans the current range once, and a random pivot shrinks the range by a constant fraction on average, so the scans add up to a small multiple of n.
- Solution 2 space: O(1) extra apart from the O(k) output copy. The loop narrows
andlo instead of recursing, so there is no call stack to grow.hi
Which One to Use
Both solutions returned the same set on over 14,000 random tests and on 10^4-point inputs. The heap leaves the input untouched and works on a stream where points arrive one at a time. It is fast when k is small, because log k is tiny. Quickselect is faster on average for a fixed array, especially when k is close to n, but it reorders the caller's array and its speed depends on random pivots. In an interview, the heap is the safer first answer, and quickselect is the follow-up when asked for better than O(n log k).
The same two methods appear in