Nearest Points to the Base

Medium

A base sits at the origin (0, 0). You are given a list of points spots, where spots[i] = [x, y], and a number count. Return the count points closest to the base by ordinary (Euclidean) distance. The answer set is guaranteed to be unique: the point in position count by distance is strictly closer than the next one. The points may be returned in any order.

Example 1

spots=[[1, -2], [3, 0], [0, 1]], count=2 → [[0, 1], [1, -2]]

The squared distances to the base are 5, 9 and 1, so the two nearest points are [0, 1] and [1, -2].

Example 2

spots=[[-4, 4], [2, 5]], count=1 → [[2, 5]]

16 + 16 = 32 versus 4 + 25 = 29, so [2, 5] is slightly closer.

Constraints

1 ≤ count ≤ len(spots) ≤ 10⁴
-10⁴ ≤ x, y ≤ 10⁴
The set of count nearest points is unique

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Geometry Array Math Divide and Conquer Quickselect Sorting Heap (Priority Queue)

Similar problems

K-th Highest Score Medium Most Common Values Medium K-th Largest Corner XOR Medium K-th Biggest Long Number Medium K-th Code by Its Last Digits Medium

Input

spots=[[1, -2], [3, 0], [0, 1]], count=2

Expected

[[0, 1], [1, -2]]

Run checks the first 3 tests in your browser. Submit checks all 72 tests on the server, hidden ones included.