#973 K Closest Points to Origin

Mediumsolve on LeetCode ↗

frequently reported atMeta Amazon Salesforce Apple Google LinkedIn

the problem

In plain words

Return the k points closest to (0, 0) by Euclidean distance, in any order.

in points = [[1,3],[-2,2]], k = 1

out [[-2,2]]

Distances² are 10 and 8.

in points = [[3,3],[5,-1],[-2,4]], k = 2

out [[3,3],[-2,4]]

1 ≤ k ≤ points.length ≤ 10⁴
-10⁴ ≤ xᵢ, yᵢ ≤ 10⁴

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTop-k with a size-k heap Quickselect

Compare squared distances (no sqrt needed). k smallest → max-heap of size k, whose root is the farthest point you're keeping.

solutions

From brute force to optimal

Sort all points by x² + y², take the first k.

Arrays.sort with comparingInt(dist²).
Copy the first k.

timeO(n log n)

Full sort.

spaceO(n)

Sorted copy.

javajava.util.*

1class Solution {2    public int[][] kClosest(int[][] points, int k) {3        int[][] copy = points.clone();4        Arrays.sort(copy, Comparator.comparingInt(p -> p[0] * p[0] + p[1] * p[1]));5        return Arrays.copyOf(copy, k);6    }7}

Keep the k closest; evict the farthest when the heap exceeds k.

Max-heap by dist².
Offer each point; poll when size > k.
Return the heap's contents.

timeO(n log k)

Heap never exceeds k + 1.

spaceO(k)

The heap.

javajava.util.*

1class Solution {2    public int[][] kClosest(int[][] points, int k) {3        // max-heap by distance²: the root is the farthest of the k kept so far4        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(dist(b), dist(a)));5        for (int[] p : points) {6            heap.offer(p);7            if (heap.size() > k) heap.poll();      // evict the farthest8        }9        return heap.toArray(new int[0][]);         // the k closest, in heap order10    }11 12    private static int dist(int[] p) {13        return p[0] * p[0] + p[1] * p[1];          // ≤ 2·10^8 for |x|, |y| ≤ 10^4: fits in int14    }15}

sim

Dry run on the plane

loading simulation…

javajava.util.*

1class Solution {2    public int[][] kClosest(int[][] points, int k) {3        // max-heap by distance²: the root is the farthest of the k kept so far4        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(dist(b), dist(a)));5        for (int[] p : points) {6            heap.offer(p);7            if (heap.size() > k) heap.poll();      // evict the farthest8        }9        return heap.toArray(new int[0][]);         // the k closest, in heap order10    }11 12    private static int dist(int[] p) {13        return p[0] * p[0] + p[1] * p[1];          // ≤ 2·10^8 for |x|, |y| ≤ 10^4: fits in int14    }15}

Partition until the k closest occupy indices 0..k−1.

Random-pivot partition by dist².
Recurse into the side containing index k − 1.

timeO(n) average, O(n²) worst

Same halving argument as Kth Largest.

spaceO(n) copy

O(1) if allowed to reorder the input.

javajava.util.*

1class Solution {2    private final Random rnd = new Random(1);3 4    public int[][] kClosest(int[][] points, int k) {5        int[][] a = points.clone();6        int lo = 0, hi = a.length - 1;7        while (lo < hi) {                          // place the k closest in a[0..k-1], any order8            int p = partition(a, lo, hi);9            if (p == k - 1) break;10            if (p < k - 1) lo = p + 1;11            else hi = p - 1;12        }13        return Arrays.copyOf(a, k);14    }15 16    private int partition(int[][] a, int lo, int hi) {   // Lomuto with a random pivot17        swap(a, lo + rnd.nextInt(hi - lo + 1), hi);18        int pivot = dist(a[hi]), store = lo;19        for (int i = lo; i < hi; i++) if (dist(a[i]) < pivot) swap(a, i, store++);20        swap(a, store, hi);21        return store;22    }23 24    private static int dist(int[] p) {25        return p[0] * p[0] + p[1] * p[1];26    }27 28    private static void swap(int[][] a, int i, int j) {29        int[] t = a[i];30        a[i] = a[j];31        a[j] = t;32    }33}

in the room

How to say it in the interview

talk track

Clarify: any order is fine, and k ≤ n. Say you'll compare x² + y², so no sqrt is needed.
Brute: sort all points by distance and take the first k — O(n log n).
Better: a max-heap of size k. Its root is the farthest point you keep, so a closer point evicts it.
Complexity: O(n log k) time, O(k) space. Mention quickselect for O(n) average if the interviewer wants faster.
Test k = n, a point at the origin, and two points at the same distance.

traps

Using Math.sqrt and doubles — slower and invites precision issues. Squared ints are exact (max 2·10⁸ fits in int).

what they ask next

Follow-ups

What if the points arrive as a stream?

Keep the same size-k max-heap. Each new point costs O(log k), and the heap always holds the k closest so far.

What if k is close to n?

Quickselect is O(n) on average whatever k is. Or flip the heap: keep the n − k farthest points in a min-heap, and the rest are the answer.

before you submit

Edge cases to test

k = n: return every point.
The origin itself has distance 0 and is always kept.
|x|, |y| ≤ 10⁴ → x² + y² ≤ 2·10⁸, which fits in an int.

practise next