K Closest Points to Origin

Problem

You are given a list of points on the plane, points[i] = [x, y], and an integer k. Return the k points that are nearest to the origin (0, 0) under Euclidean distance. The result may be in any order, and the answer is guaranteed to be unique (there are no ties at the k-th boundary that would make the set ambiguous).

• Up to around ten thousand points, and k is always a valid count for the given list.
• Coordinates fit comfortably in a normal int, positive or negative.

Examples

• points = [[2,4],[-3,1]], k = 1 → [[-3,1]]. Squared distances are 20 and 10, so (-3, 1) is closer.
• points = [[4,2],[6,-3],[-1,5]], k = 2 → [[4,2],[-1,5]] in any order. Squared distances 20, 45, 26; the two smallest are 20 and 26.
• points = [[0,0]], k = 1 → [[0,0]]. The origin itself at distance 0.

Hints

1. You never need the actual distance, only a way to compare two points. What can you drop from the formula?
2. Sorting all points is O(n log n). If k is small, can you avoid ordering points that will never be in the answer?
3. Max-heap of size k keyed on squared distance (O(n log k)), or quickselect on squared distance (O(n) average).