K Closest Points to Origin

Given a list of points (x, y) on the plane, return the k closest to the origin. Distance is Euclidean, but since the comparison is monotonic, the machine can rank by squared distance x*x + y*y and never compute a square root.

The key insight: this is "kth largest" in disguise. A max-heap of size k keyed by squared distance keeps the k closest: push each point, and when the heap exceeds k, evict the point farthest from the origin (the heap root). At the end, the heap holds exactly the k closest points. This avoids sorting all n points when k is small.

Approach in steps:

1. Push each point with its squared distance onto a max-heap (negate to use Python's min-heap).
2. When the heap exceeds k, pop the root — the current farthest.
3. Return the remaining points.

import heapq
 
def kClosest(points, k):
    heap = []
    for x, y in points:
        d = x * x + y * y
        heapq.heappush(heap, (-d, x, y))
        if len(heap) > k:
            heapq.heappop(heap)
    return [[x, y] for _, x, y in heap]

Time is O(n log k), space O(k). For large k a plain sort at O(n log n) is competitive; the heap wins when k is small.

Trickiest edge case: ties on distance. Points equidistant from the origin are interchangeable — any k of them satisfy the problem, so the machine does not need a tie-break rule. Also, when k equals n, eviction never fires and the answer is the full set; the heap must tolerate len(heap) == k without popping.