Problem 36 · Heaps

K Closest Points to Origin

MediumClassic DSA & systems

01Problem

Given a list of 2D points and an integer k, return the k points closest to the origin (any order).

02Key insight

Compare squared distances (no sqrt); a size-k max-heap gives O(n log k) and streams well, heapq.nsmallest does exactly this.

03Solution

solution.pypython14 lines

import heapq

def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    # Max-heap of size k on negative squared distance.
    heap: list[tuple[int, int]] = []
    if k <= 0:
        return []
    for i, (x, y) in enumerate(points):
        entry = (-(x * x + y * y), i)
        if len(heap) < k:
            heapq.heappush(heap, entry)
        elif entry > heap[0]:
            heapq.heapreplace(heap, entry)
    return [points[i] for _, i in heap]

Try it first.

TimeO(n log k)

SpaceO(k)

tests.py · 3 passing

tests.pypython3 lines

assert k_closest([[1, 3], [-2, 2]], 1) == [[-2, 2]]
assert sorted(k_closest([[3, 3], [5, -1], [-2, 4]], 2)) == [[-2, 4], [3, 3]]
assert k_closest([[1, 1]], 0) == []

04Staff-level follow-up

Billions of points, many queries with different origins? Build a spatial index (k-d tree, geohash/S2 cells) and search outward from the query cell instead of scanning.