K Closest Points to Origin

Problem

Given an array of 2-D points and an integer k, return the k points closest to the origin (0, 0) by Euclidean distance. The answer may be in any order.

Constraints

• 1 ≤ points.length ≤ 10⁴
• 1 ≤ k ≤ points.length
• −10⁴ ≤ x, y ≤ 10⁴

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

class Solution:
    def kClosest(self, points, k):
        points.sort(key=lambda p: p[0]*p[0] + p[1]*p[1])
        return points[:k]

Java

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        // Max-heap by squared distance to the origin. Keep size <= k by
        // popping the FARTHEST whenever we exceed k. The k that remain
        // are the k closest.
        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[] point : points) {
            heap.offer(point);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        int[][] result = new int[k][];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = heap.poll();
        }
        return result;
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.