Room 04 · The Grind — Heap / Priority Queue

K Closest Points to Origin

MEDIUM✓ CHIP-TIMEDLC #973 — FULL STATEMENT

The briefingthe full drill, in my own words

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.

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.

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

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

The hintstake 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 boardthe 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 splitstwo 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-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED