Nearest k Values

Medium

You are given a list of integers values sorted in non-decreasing order, a number k and a number target. Pick the k elements closest to target and return them in ascending order. Element a is closer than element b if |a - target| < |b - target|; when the distances are equal, the smaller value counts as closer. Repeated values are separate elements, so several of them may be picked.

Example 1

values=[2, 4, 6, 8, 10], k=3, target=7 → [4, 6, 8]

6 and 8 are 1 away, then 4 and 10 are both 3 away, and the smaller one, 4, wins.

Example 2

values=[1, 1, 3, 20], k=2, target=30 → [3, 20]

20 is the closest, followed by 3.

Example 3

values=[-5, 0, 5], k=1, target=-1 → [0]

Constraints

1 ≤ k ≤ len(values) ≤ 10⁴
-10⁴ ≤ values[i], target ≤ 10⁴
values is sorted in non-decreasing order

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Binary Search Sorting Sliding Window Heap (Priority Queue)

Similar problems

Ranked Prime Ratios Medium Studios for Recording Sessions Medium Triples Under a Limit Medium K-th Smallest in a Sorted Grid Medium Warm Every Cabin Medium

Input

values=[2, 4, 6, 8, 10], k=3, target=7

Expected

[4, 6, 8]

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