447. Find K Closest Elements
You are given an integer array arr sorted in ascending order, and two integers k and x. Your function receives arr, k, and x, and returns the k elements of arr that are closest to x, reported in ascending order.
Closeness breaks ties toward the smaller element: a beats b when |a − x| < |b − x|, or when the distances are equal and a < b.
Under that rule the winners always form one contiguous window of the array, so the answer is unique. x itself does not have to appear in arr.
Example 1:
Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
Output: [1, 2, 3, 4]
Explanation: Distances to 3 are [2, 1, 0, 1, 2]. Three elements (2, 3, 4) are clear winners; 1 and 5 are tied at distance 2, and the tie goes to the smaller value 1.
Example 2:
Input: arr = [2, 4, 5, 9], k = 2, x = 6
Output: [4, 5]
Explanation: Distances are [4, 2, 1, 3], so the two closest values are 5 and 4 — reported ascending as [4, 5].
Constraints:
- 1 ≤ k ≤ arr.length ≤ 10⁴
- arr is sorted in ascending order (duplicates allowed)
- -10⁴ ≤ arr[i], x ≤ 10⁴
Hints:
The winners always form a contiguous window of the sorted array: if some element is picked, everything lying between it and x is at least as close, so it is picked too. The task is really "find the best window of length k".
Binary-search the window's left edge lo over [0, n − k]. To compare the window starting at mid against the one starting at mid + 1, compare x − arr[mid] with arr[mid + k] − x (signed, no absolute values): if x − arr[mid] > arr[mid + k] − x, the left element loses to the incoming right one, so move lo past mid; otherwise keep hi at mid. O(log(n − k) + k) total.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: arr = [1, 2, 3, 4, 5], k = 4, x = 3
Expected output: [1, 2, 3, 4]