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.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

03

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

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.