K Closest Points to Origin

medium

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points is the Euclidean distance. You may return the answer in any order.

Test Cases

Copy an input into the main harness and Run to verify

Input

points = [[1,3],[-2,2]], k = 1

Expected Output

[[-2,2]]

Explanation: The distance of (-2,2) to the origin is sqrt(8), which is less than sqrt(10) for (1,3).

Input

points = [[3,3],[5,-1],[-2,4]], k = 2

Expected Output

[[3,3],[-2,4]]

Constraints

1 <= k <= points.length <= 10^4
-10^4 <= xi, yi <= 10^4

Hints

Hint 1 — click to reveal

You never need the actual distance — comparing x² + y² preserves the ordering and avoids floating point.

Hint 2 — click to reveal

A max-heap capped at size k beats sorting when k is much smaller than n.

Java Compiler