K closest points to origin

Problem Given points on a plane and k, return the k points closest to the origin (any order).

Input / Output

• Input: int[][] points, int k. Output: k closest points.

Constraints

• Up to 10^4 points; compare SQUARED distances (no sqrt — avoids float issues).

Example

• points = [[1,3],[-2,2]], k = 1 → [[-2,2]] (4+4=8 < 1+9=10).

Expected approach

• Max-heap of size k keyed by squared distance: push each point, pop when size exceeds k — O(n log k) time, O(k) space; the heap holds the answer. Contrast with min-heap of all points (O(n + k log n), O(n) space) and know when each wins (k << n → size-k max-heap; streaming input → only the max-heap works). Quickselect partitioning by distance gives O(n) average — the senior-level answer. Sorting is the O(n log n) baseline.