K Closest Points to Origin

Given points on a 2D plane, return the k points with the smallest Euclidean distance from the origin. To make the output deterministic, sort the selected points by distance ascending, then x ascending, then y ascending.

Input Format

points = list of 2D points, k = number of points to return

Output Format

k closest points sorted by distance ascending, then x, then y

Constraints

  • 1 <= points.length <= 10^5
  • -10^4 <= points[i][0], points[i][1] <= 10^4
  • 1 <= k <= points.length

Examples

Example 1:

Input:

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

Output:

[[-2,2],[2,-2]]

Explanation:

Both selected points have distance squared 8, which is smaller than 10 for [1,3].

Example 2:

Input:

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

Output:

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

Explanation:

Distances are 18, 26, and 20; the two smallest are 18 and 20.

Loading...
K Closest Points to Origin - Heap DSA Problem