Find k Closest Elements to Target

Given a sorted list and a target, return exactly k values with the smallest absolute difference.

binary-search sorting two-pointers lists

Write a function `find_k_closest(arr, k, target)`. The input `arr` is a list of integers sorted in ascending order. The integer `k` satisfies `1 <= k <= len(arr)`. The target can be any integer. The function must return a list of exactly `k` integers from `arr` such that these integers are the `k` elements with the smallest absolute difference to `target`. If there is a tie (two numbers have the same absolute difference), choose the smaller number. The returned list must be in the same order as they appear in `arr` (the original sorted order). The solution should be efficient; an O(n) or O(k + log n) approach is acceptable.

Constraints

The input list length is at most 10^5. Values can be negative or positive. The function should handle duplicates in `arr`. Return the elements themselves, not indices.

Example

>>> find_k_closest([1,2,3,4,5], 4, 3)
[1,2,3,4]
>>> find_k_closest([1,2,3,4,5], 4, -1)
[1,2,3,4]
>>> find_k_closest([1, 2, 3, 4, 5], 4, 6)
[2,3,4,5]

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

You can sort the array by a custom key: distance to target, then the value itself.

After selecting the k closest, sort the selection by their original index order.

If using binary search, find the insertion point and expand a window around it.

Watch for cases where the target is far outside the array range.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.