K Closest Points to Origin

You are given an array points, where points[i] = [x, y] is a point on the plane, and an integer k. Return the k points closest to the origin (0, 0), measured by Euclidean distance. The answer may be in any order, and the problem guarantees it is unique. This is LeetCode 973.

Limits: 1 <= k <= points.length <= 10^4 and -10^4 <= x, y <= 10^4.

The page gives two solutions. Solution 1 keeps the k best points in a max-heap. Solution 2 uses quickselect to move the k closest points to the front of the array.

Example 1
Input: points = [[1, 3], [-2, 2]], k = 1
Output: [[-2, 2]]
Example 2
Input: points = [[3, 3], [5, -1], [-2, 4]], k = 2
Output: [[3, 3], [-2, 4]]

How to Think About It

Step 1: Compare squared distances

The distance of (x, y) is sqrt(x*x + y*y). The square root never changes which of two points is closer, so comparing x*x + y*y is enough. In Example 1 the values are 10 and 8, so [-2, 2] wins.

With coordinates up to 10^4 in size, the largest squared distance is 2 × 10^8. That fits in an int, whose limit is about 2.1 × 10^9.

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 Kth Largest Element in a Stream, with the heap direction flipped because we want the smallest values. The heap introduction covers the operations.

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. The squared distances are 18 for [3, 3], 26 for [5, -1] and 20 for [-2, 4].

Point addedSquared distanceHeap size after offerPolled (farthest)Heap after (distances)
[3, 3]181nothing{18}
[5, -1]262nothing{26, 18}, top 26
[-2, 4]203[5, -1] (26){20, 18}, top 20

The heap ends with [3, 3] and [-2, 4], which is the answer.

Solution 1: Max-Heap of Size k

kClosest pushes every point into a max-heap ordered by squared distance and removes the top whenever the heap holds k + 1 points.

  • The comparator: Integer.compare(dist(b), dist(a)) reverses the natural order, so the farthest kept point sits on top and is the one poll removes.
  • The size rule: after each offer, a heap of k + 1 points loses its farthest one. The k points left are always the k closest of those seen so far.
  • Building the result: heap.toArray(new int[0][]) returns the kept points in heap order, which is allowed because any order is accepted.
  • k equal to n: nothing is ever polled, and every point is returned. With [[0, 1], [1, 0]] and k = 2 both points come back.

A common mistake is to use the default PriorityQueue, which is a min-heap. Then poll throws away the closest point each time. On Example 2 it returns [[-2, 4], [5, -1]], the two farthest points.

Java
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 in place until the k closest points occupy indices 0 to k - 1, then copies them out.

  • Three-way partition: one pass over [lo, hi] leaves points closer than the pivot in [lo, lt), points at the same distance in [lt, gt], and farther points in (gt, hi].
  • Choosing a side: if index k - 1 is left of lt, the search continues in the closer part. If it is right of gt, it continues in the farther part. Otherwise index k - 1 holds a pivot-distance point and the front k are the answer.
  • 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] for i from 0 to 9999 with k = 1, each round removes only one point. That run made 50,015,000 distance computations. With a random pivot, the average over 20 runs was about 19,800.

Java
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 offer and at most one poll, and both cost O(log k) because the heap never holds more than k + 1 points.
  • 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 lo and hi instead of recursing, so there is no call stack to grow.

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 Kth Largest Element in an Array, and a frequency version of keep-k is Top K Frequent Elements.