K Closest Points to Origin

K Closest Points to Origin is a classic "top-k" problem. It teaches two reusable moves: scoring items by a cheap comparable key, and using a heap to pull out the smallest few without sorting everything.

The slow way first

The obvious idea: compute every distance, sort all the points by distance, then take the first k. That works and is simple, but sorting costs O(n log n) even when k is tiny. If you only need the 3 closest out of a million points, sorting all million is wasteful.

The question to ask: do I really need the whole array ordered? No — I only need the k smallest. A heap gives me exactly that.

The idea: score, then heap

First, a trick that simplifies everything: distance is √(x² + y²), but the square root is monotonic — it never changes which point is closer. So we compare x² + y² directly and skip the sqrt entirely (also avoiding floating point).

Then push every (dist, point) onto a min-heap and pop k times. Each pop hands back the smallest remaining distance, so the first k pops are the k closest points.

The key insight: we never need a true distance, only a comparable score. Squared distance is cheaper and orders points identically.

Walk through it

Step through the animation. We score each point: [1, 3] gives 1 + 9 = 10, and [-2, 2] gives 4 + 4 = 8. Both go onto the min-heap. Since k = 1, we pop once and get the smallest distance, 8, which belongs to [-2, 2] — the answer.

Pseudocode

heap = empty min-heap
for each point (x, y):
    dist = x*x + y*y          # squared distance, no sqrt needed
    push (dist, point) onto heap
result = empty list
repeat k times:
    pop the smallest (dist, point) off the heap
    add point to result
return result

The Python solution

def k_closest(points, k):
    heap = []
    for x, y in points:
        dist = x * x + y * y
        heapq.heappush(heap, (dist, [x, y]))
    result = []
    for _ in range(k):
        _, point = heapq.heappop(heap)
        result.append(point)
    return result

• dist = x * x + y * y is the squared distance — comparable to a true distance but cheaper.
• heapq is Python's binary min-heap; pushing a (dist, point) tuple orders entries by dist first.
• The first loop builds the heap in O(n log n) (or O(n) with heapify).
• The second loop pops k times; each pop is O(log n) and returns the next-smallest distance.
• We collect k points and return them — the k closest to the origin.

Complexity

For small k, a smarter variant keeps a max-heap of size k: push each point and, if the heap grows past k, pop the farthest. That bounds the heap to k entries and runs in O(n log k).

When this pattern shows up

Practice