K Closest Points to Origin

mediumTests passed 2026-11-11v1.0.0
TC: O(N log k)|SC: O(k)
HeapsOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Maintain a bounded max-heap of size `k` keyed by squared Euclidean distance `x^2 + y^2` (skip `sqrt` to avoid floats). Any larger candidate evicts itself if `len > k` (or Quickselect for O(N) expected time).

2. Complexity Bounds & Proof

Heap size never exceeds k; each of N points triggers at most one O(log k) push/pop.

3. Minimal Idiomatic Code

def kClosest(points: list[list[int]], k: int) -> list[list[int]]:
    h = []
    for i, (x, y) in enumerate(points):
        dist = -(x * x + y * y)
        if len(h) < k:
            heapq.heappush(h, (dist, i, x, y))
        elif dist > h[0][0]:
            heapq.heapreplace(h, (dist, i, x, y))
    return [[x, y] for _, _, x, y in h]

4. Failure Modes & Interview Follow-ups

Pitfalls:- Comparing raw `sqrt` floats loses precision and wastes cycles; `x*x + y*y` is strictly monotonic for non-negative distances. - Using a min-heap instead of max-heap costs O(N log N) instead of O(N log k).
Follow-ups:- Quickselect partitions points in-place in O(N) average time when k can be large.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Top K Frequent Elements (O(N))Kth Largest Element in a Stream (O(N log k))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.