K Closest Points to Origin

LeetCode 973 • Medium • Heaps

Input: points = [[1,1],[2,2],[3,3],[4,4]], k = 2 → Output: [[1,1],[2,2]]
Max-heap of size k by distance²: push each point, pop farthest when len>k.

TimeO(n log k)n pushes, heap size k

SpaceO(k)max-heap size

Heap: []Processed: 0/4

Current point

In k-heap

Popped / skipped

Origin (0,0)

Max-heap

—

Speed:

Ready

Press Play. Max-heap of size k=2 by distance²; pop farthest when full.

✎ Whiteboard

Size:3

⌨ Type It

Max-heap of size k keeps k closest. Negate dist for Python min-heap trick.

═══ K CLOSEST — MAX HEAP SIZE K ═══

PATTERN ▸ Max-heap of size k O(n log k) · O(k)

① LOOP

heappush(heap, (-dist, x, y))

if len(heap) > k: heappop(heap)

② RETURN

[(x,y) for _,x,y in heap]

▼ your implementation ▼

Verify your solution: