Sign in
Skip to solution
mediumDSA

How do you find the k closest points to the origin?

1.1k views
01

Understand the problem

Explain k-closest with a heap.

heapgeometry
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Keep a max-heap of size k by squared distance (no need for sqrt); push each point and pop the farthest when size exceeds k. O(n log k). Quickselect on distances gives average O(n) when a single batch result is enough.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Max-heap of size k
Run Playground
import heapq

def k_closest(points, k):
    heap = []                       # max-heap via negative distance
    for x, y in points:
        d = x * x + y * y
        heapq.heappush(heap, (-d, [x, y]))
        if len(heap) > k:
            heapq.heappop(heap)     # drop the farthest
    return sorted(p for _, p in heap)


# --- demo ---
print(k_closest([[1, 3], [-2, 2], [5, 8], [0, 1]], 2))   # [[-2, 2], [0, 1]]
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 30 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track