K Closest Points to Origin

Problem

Ride-sharing and logistics apps rank driver or delivery candidates by proximity to a pickup location. Returning the K nearest from a large pool efficiently - without sorting all candidates - is the core challenge. Given an array of 2D points, return the k points closest to the origin (0, 0). Distance is Euclidean; return any valid set if multiple answers tie.

Input: points = [[1,3],[-2,2],[5,8],[0,1]], k = 2   → [[-2,2],[0,1]]
Input: points = [[3,3],[5,-1],[-2,4]], k = 2   → [[3,3],[-2,4]]
Input: points = [[0,0],[1,1]], k = 1   → [[0,0]]

Solution

Approach: size-K max-heap keyed on negated squared distance.

Two ideas combine. First, comparing distances never needs sqrt: since the square root is monotonic, ordering by x*x + y*y ranks points identically to ordering by true Euclidean distance, and stays in integer arithmetic. Second, the top-K pattern keeps only the K nearest. Here we want the K smallest distances, so we need a max-heap whose root is the farthest survivor - the element to drop when a closer point appears. Python's heapq is a min-heap, so we negate: pushing (-dist, x, y) makes the largest actual distance the most negative value and therefore the heap root. Each point is pushed once; whenever the heap exceeds K, one pop discards the current farthest. After the scan, the heap holds the K closest points, and [[x, y] for _, x, y in max_heap] reconstructs them.

Trace [[1,3],[-2,2],[5,8],[0,1]], K=2 (distances 10, 8, 89, 1): push (-10,..) and (-8,..); push (-89,..) then pop the root -10; push (-1,..) then pop -89. The heap keeps [-2,2] and [0,1].

Edge cases: ties in distance are acceptable since any valid K closest may be returned. When K equals the point count, no pop fires and all points come back. Storing (x, y) in the tuple avoids a second lookup at extraction.

Complexity: O(n log K) time, O(K) space - n points, each an O(log K) push/pop on a K-capped heap.