All problems

K Closest Points to Origin

Medium · heap

You are given a list of points on a flat grid, points, where each point is [x, y], and an integer k. Return the k points that are closest to the origin (0, 0), using ordinary straight-line (Euclidean) distance.

To make the answer exactly one list, sort it: put points with a smaller distance first. If two points are the same distance from the origin, put the one with the smaller x first, and if x is also equal, the one with the smaller y first.

The same point can appear more than once in points. Each copy is a separate point, so it can appear more than once in the answer. When several points tie for the last place among the k, keep the ones that come first in the sorted order described above.

Examples

Example 1

Input: points = [[3, 3], [1, 0], [-2, 2]], k = 2

Output: [[1, 0], [-2, 2]]

The squared distances are 18, 1 and 8, so the two closest points are [1, 0] and [-2, 2], in that order.

Example 2

Input: points = [[0, 2], [2, 0], [-2, 0], [0, -2]], k = 3

Output: [[-2, 0], [0, -2], [0, 2]]

All four points are the same distance away, so the tie is broken by x and then y. [2, 0] is last in that order and misses out.

Example 3

Input: points = [[5, 5]], k = 1

Output: [[5, 5]]

Constraints