DSA problem
Find K Closest Elements
Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order. An integer a is closer to x than an integer b if |a - x| < |b - x|, or |a - x| == |b - x| and a < b.
The straightforward O(n + k) solution uses two pointers from both ends of the array, repeatedly discarding the worse endpoint. But there is a beautiful O(log(n - k) + k) approach: binary search for the left boundary of the answer window directly.
The answer is a contiguous window of length k inside arr (any non-contiguous selection of k values must be inferior because a sorted slice is always tighter to a single point x). So the search space for the window's start index is [0, n - k]. For a candidate start mid, compare it to mid + 1 by checking whether x - arr[mid] or arr[mid + k] - x is larger: if x - arr[mid] > arr[mid + k] - x, the window starting at mid + 1 is strictly better, so move lo right; otherwise narrow hi to mid.
When the loop ends, lo == hi is the start of the best window, and you return arr[lo..lo+k]. The binary search is O(log(n - k)); building the result slice is O(k). Total time O(log(n - k) + k) and O(1) extra space outside the output.
Examples
arr = [1,2,3,4,5], k = 4, x = 3[1,2,3,4]arr = [1,1,2,3,4,5], k = 4, x = -1[1,1,2,3]arr = [1,3], k = 1, x = 2[1]Constraints
- 1 <= k <= arr.length
- 1 <= arr.length <= 10^4
- arr is sorted in ascending order.
- -10^4 <= arr[i], x <= 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.