K Closest Points to Origin

Medium Heaps Top K / Kth Largest / Smallest Original on LeetCode

K Closest Points to Origin is a medium heaps problem solved with the top k / kth largest / smallest pattern. The best approach, optimal (quickselect), runs in O(n) average, O(n²) worst case time and O(1) extra space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (sort by distance) up.

Problem

You are given an array points, where points[i] = [x, y] is a point on the 2D plane, and an integer k. Return the k points that are closest to the origin (0, 0).

Distance is the usual straight-line (Euclidean) distance, sqrt(x² + y²). The input guarantees that the set of the k closest points is unique, and you may return those points in any order.

Examples

Example 1

Input
points = [[3, 4], [-1, 2], [6, -1], [0, -3]], k = 2
Output
[[-1, 2], [0, -3]]
Why
Squared distances are 25, 5, 37 and 9, so the two smallest belong to [-1, 2] and [0, -3].

Example 2

Input
points = [[2, 2], [-5, 0], [1, -1]], k = 1
Output
[[1, -1]]
Why
[1, -1] is at squared distance 2, closer than 8 and 25.

Example 3

Input
points = [[7, 7], [0, 1]], k = 2
Output
[[7, 7], [0, 1]]
Why
When k equals the number of points, every point is returned (in any order).

Constraints

  • 1 <= k <= points.length <= 10^4
  • points[i].length == 2
  • -10^4 <= x, y <= 10^4
  • The answer is unique: the k-th and (k + 1)-th smallest distances are different.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (sort by distance)O(n log n)O(n)
Better (max-heap of size k)O(n log k)O(k)
Optimal (quickselect)O(n) average, O(n²) worst caseO(1) extra

1Brute force (sort by distance)

TimeO(n log n)Sorting all n points dominates.
SpaceO(n)The sort and the copied answer.

Sort all points by their squared distance to the origin and return the first k.

  1. Sort points by x² + y² ascending.
  2. Return the first k points.
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int[][] sorted = points.clone();
        Arrays.sort(sorted, (a, b) -> (a[0] * a[0] + a[1] * a[1]) - (b[0] * b[0] + b[1] * b[1]));
        return Arrays.copyOfRange(sorted, 0, k);
    }
}

2Better (max-heap of size k)

TimeO(n log k)n pushes and at most n pops on a heap that never exceeds k + 1 points.
SpaceO(k)The heap holds at most k + 1 points.

Scan the points once while keeping the k closest seen so far in a max-heap ordered by distance. The heap's top is the farthest of those k, so a new point only matters if it is closer than the top; then it replaces the top.

  1. Create a max-heap keyed by x² + y².
  2. For each point: push it; if the heap now has more than k points, pop the farthest.
  3. Return the k points left in the heap.
class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]));
        for (int[] p : points) {
            heap.offer(p);
            if (heap.size() > k) heap.poll();
        }
        int[][] res = new int[k][];
        for (int i = 0; i < k; i++) res[i] = heap.poll();
        return res;
    }
}

3Optimal (quickselect)

TimeO(n) average, O(n²) worst caseWith a random pivot each round keeps about half of the remaining range on average: n + n/2 + n/4 + … = O(n). Very unlucky pivots could cost O(n²).
SpaceO(1) extraPartitioning swaps points in place; only a few indices are kept (plus the returned copy).

We only need the k closest points as a group, not in order. Quickselect picks a random pivot, partitions the range so that closer points come before it and the rest after it, and then continues only in the part that contains index k - 1. When the pivot lands exactly on k - 1, the first k positions hold the answer.

  1. lo = 0, hi = n - 1.
  2. While lo < hi: choose a random pivot in [lo, hi] and partition the range by distance; let p be the pivot's final index.
  3. If p == k - 1 stop; if p < k - 1 set lo = p + 1; otherwise set hi = p - 1.
  4. Return the first k points.
class Solution {
    private final Random rnd = new Random(7);

    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;
    }

    private int partition(int[][] a, int lo, int hi) {
        swap(a, lo + rnd.nextInt(hi - lo + 1), hi);
        int pivot = dist(a[hi]), store = lo;
        for (int i = lo; i < hi; i++) {
            if (dist(a[i]) < pivot) swap(a, i, store++);
        }
        swap(a, store, hi);
        return store;
    }

    public int[][] kClosest(int[][] points, int k) {
        int lo = 0, hi = points.length - 1;
        while (lo < hi) {
            int p = partition(points, lo, hi);
            if (p == k - 1) break;
            if (p < k - 1) lo = p + 1;
            else hi = p - 1;
        }
        return Arrays.copyOfRange(points, 0, k);
    }
}

Edge cases to test

  • k equal to the number of points: return them all
  • Points on an axis or at the origin itself
  • Different points at the same distance (only allowed when they are all inside or all outside the answer)
  • Coordinates up to 10^4: the squared distance reaches 2 · 10^8, which still fits in a 32-bit int

Hints

Hint 1

You never need the real distance: comparing x² + y² gives the same order and avoids square roots.

Hint 2

Sorting works but does more than needed. A max-heap that never holds more than k points keeps exactly the k best seen so far.

Hint 3

Quickselect partitions the array around a pivot distance like quicksort, but only recurses into the side that contains position k - 1, which gives O(n) on average.

FAQ

What is the best time complexity for K Closest Points to Origin?

Optimal (quickselect) runs in O(n) average, O(n²) worst case time and O(1) extra extra space. With a random pivot each round keeps about half of the remaining range on average: n + n/2 + n/4 + … = O(n). Very unlucky pivots could cost O(n²).

Which pattern does K Closest Points to Origin use?

It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in an Array, Kth Largest Element in a Stream, Top K Frequent Words.

Is there a brute force solution for K Closest Points to Origin?

Yes. Brute force (sort by distance) takes O(n log n) time and O(n) space. Sort all points by their squared distance to the origin and return the first k.

Which edge cases should I test for K Closest Points to Origin?

k equal to the number of points: return them all; Points on an axis or at the origin itself; Different points at the same distance (only allowed when they are all inside or all outside the answer); Coordinates up to 10^4: the squared distance reaches 2 · 10^8, which still fits in a 32-bit int.