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.

Example 1:

Input: points = [[2,4],[-1,2],[6,5],[0,1]], k = 2
Output: [[-1,2],[0,1]]
Explanation: distances 20, 5, 61, 1 - the two closest are [-1,2] and [0,1].

Example 2:

Input: points = [[4,4],[6,-1],[-3,4]], k = 2
Output: [[4,4],[-3,4]]

Example 3:

Input: points = [[0,0],[2,2]], k = 1
Output: [[0,0]]

Constraints:

• 1 <= k <= points.length <= 10^3
• -100 <= x[i], y[i] <= 100

Solution Breakdown

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 [[2,4],[-1,2],[6,5],[0,1]], K=2 (distances 20, 5, 61, 1): push (-20,..) and (-5,..); push (-61,..) then pop the root -20; push (-1,..) then pop -61. The heap keeps [-1,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.