K Closest Points to Origin

Find the k closest points to the origin.

Pattern

Max-Heap of Size K

This problem follows the Max-Heap of Size K pattern, commonly found in the Heap / Priority Queue category. Recognizing this pattern is key to solving it efficiently in an interview setting.

Approach

How to Solve It

Use a max-heap of size k. If new point is closer than heap top, replace.

Key Insight

Use squared distances to avoid computing square roots — relative ordering is preserved. A max-heap of size k evicts the farthest point.

Step-by-step

1Use a max-heap of size k (or min-heap with negated distances)
2For each point, compute its squared distance from origin
3If heap size < k, push the point
4If distance < heap root distance, replace the root
5Return all k points in the heap

Pseudocode

heap = []
for x, y in points:
    dist = x*x + y*y
    if len(heap) < k:
        heappush(heap, (-dist, [x, y]))
    elif -dist > heap[0][0]:
        heapreplace(heap, (-dist, [x, y]))
return [p for _, p in heap]

Complexity Analysis

Time Complexity

O(n log k)

Space Complexity

O(k)

More Heap / Priority Queue Problems

EasyKth Largest Element in a StreamMin-Heap of Size K EasyLast Stone WeightMax-Heap Simulation MediumTask SchedulerGreedy + Heap HardFind Median from Data StreamTwo Heaps

Master this pattern with YeetCode

Practice K Closest Points to Origin and similar Heap / Priority Queue problems with flashcards. Build pattern recognition through active recall.

Practice this problem

Previous← Last Stone Weight NextTask Scheduler →