K Closest Points to Origin
Module 19 · Heaps
Problem
Given an array of points where points[i] = [xi, yi] represents a
point on the X-Y plane, return the k points closest to the origin
(0, 0), in any order. Distance is the usual Euclidean distance.
(LeetCode 973.)
Examples
Example 1
points = [[1,3],[-2,2]], k = 1Output[[-2,2]]Example 2
points = [[3,3],[5,-1],[-2,4]], k = 2Output[[3,3],[-2,4]]Constraints
1 ≤ k ≤ points.length ≤ 10⁴, coordinates in ±10⁴.
Attempt it first
This is structurally the sibling of Kth Largest Element in a Stream — both maintain a fixed-size-k heap of "the best k seen so far" — but here the heap orientation FLIPS. Before opening anything, work out precisely why: in Kth Largest, you wanted a min-heap so the smallest of your current top-k sat at the root, ready to be evicted the instant something larger arrived. Here, what quantity do you want sitting at the root, ready for eviction, as you scan through candidate points?