Heaps Top K

408. K Closest Points to Origin

You are given a list of points on a plane, where points[i] = [x, y], and an integer k. Return the k points that are closest to the origin (0, 0).

The distance from a point (x, y) to the origin is the straight-line distance, √(x² + y²).

The answer is always unique: the k-th closest point is closer than every point left out. You may return the points in any order. The examples list them sorted by x, then by y.

Example 1

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

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

Explanation: The squared distances are 25, 5, 26, 9 and 8. The three smallest are 5, 8 and 9, and they belong to [-1,2], [2,2] and [0,-3].

Example 2

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

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

Explanation: Three points are at distance 1 and the fourth is farther, so the answer is those three. Points at the same distance are fine inside the answer.

Example 3

Input: points = [[10000000, -10000000], [-9999999, 10000000]] k = 1

Output: [[-9999999,10000000]]

Explanation: Both points are far out: x² + y² is about 2 × 10¹⁴ for each. The second one is a little closer.

Check your understanding

Work out the answer for this input before you write any code.

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

Constraints

1 ≤ points.length ≤ 10⁵
points[i].length = 2
-10⁷ ≤ x, y ≤ 10⁷
1 ≤ k ≤ points.length
The k-th closest point is closer to the origin than every point outside the answer.

Clarifying questions

What you would ask an interviewer before writing any code.