K Closest Points to Origin

MEDIUM✓ CHIP-TIMEDLC #973 — FULL STATEMENT ↗

The drill: Pick the k points nearest the origin out of a scattered set — nearest meaning straight-line distance, no fixed order required among the ones you return.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A scattered set of 2D points arrives along with a count k, and the job is picking out the k points that sit closest to the origin.

Closeness means ordinary straight-line distance, and the k returned points can come back in any order among themselves — nothing about their relative sequence gets checked.

Ties at the boundary distance resolve however the picking method naturally breaks them, since any valid set of k closest points is accepted.

EX 01

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

→ [[-2, 2]]

THE CLOSER OF TWO POINTS

EX 02

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

→ [[3, 3], [-2, 4]]

EXCLUDES THE FARTHEST OF THREE

EX 03

points = [[0, 0]] · k = 1

→ [[0, 0]]

THE ORIGIN ITSELF, DISTANCE ZERO

point counts run up to several thousand
coordinates can be negative, zero, or positive
k never exceeds the number of points supplied
the k returned points may come back in any order

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Distance never needs a square root here — comparing squared distances puts points in the exact same order without ever calling sqrt.

HINT 2 THE STRUCTURE

Sorting every point by distance and slicing the first k works, but the far-away points still get fully sorted even though nobody asked about their order.

HINT 3 ONE STEP FROM THE ANSWER

Keep a max-heap capped at size k, keyed by squared distance. Push each point in, evict the current farthest whenever the heap overflows past k — what's left are the k closest.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE FARTHEST GETS EVICTEDPATTERN · MAX-HEAP OF SIZE Kpoints = [(-5,4), (3,-3), (2,2), (-1,-1), (6,0)] · k = 2

(-5,4)

(3,-3)

(2,2)

(-1,-1)

(6,0)

THE HEAP (SIZE ≤ K, BY DISTANCE²)

— empty —

STEP 1

k=2. Keep a max-heap capped at size 2, keyed by squared distance — the farthest point gets evicted whenever it overflows.

STEP 1 / 7 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/k-closest-points-to-origin.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []  # max-heap of size k, via negated distance
        for x, y in points:
            d = x * x + y * y
            heapq.heappush(heap, (-d, x, y))
            if len(heap) > k:
                heapq.heappop(heap)
        return [[x, y] for _, x, y in heap]

TIME O(N LOG K)SPACE O(K)PYTHON · RACE PACE · 9 LN

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        ordered = sorted(points, key=lambda p: p[0] * p[0] + p[1] * p[1])
        return ordered[:k]

TIME O(N LOG N)SPACE O(N)PYTHON · TRAINING PACE · 4 LN

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();
            }
        }
        return heap.toArray(new int[heap.size()][]);
    }
}

TIME O(N LOG K)SPACE O(K)JAVA · RACE PACE · 13 LN

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

TIME O(N LOG N)SPACE O(N)JAVA · TRAINING PACE · 7 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED