MiddleCodeOccasionalNot answered yet
K elements closest to a value x in a sorted array
Given a sorted array arr, an integer k, and a value x, return the k elements closest to x, sorted ascending. On a tie prefer the smaller value.
Requirements:
- O(log n + k): binary-search the insertion point, then expand a window of two pointers.
std::vector<int> findClosestElements(const std::vector<int>& arr, int k, int x) {
// your code here
}Write the implementation.
Binary-search the position of x, then grow a size-k window. Each step compare the boundaries' distance to x; if x - arr[left-1] <= arr[right] - x move left, else right. The <= favours the smaller value on a tie. The window stays sorted. O(log n + k).
- ✗Returning the k elements only to the right of x instead of the closest on both sides
- ✗Using
<instead of<=and breaking the smaller-value tie-break - ✗Letting the left/right pointers run past the array bounds
- →How does this differ from finding k closest to a[index] rather than a free value x?
- →Why does the window remain contiguous throughout?
Contents
Task
Return the k elements of the sorted array closest to value x, in O(log n + k).
Solution
std::vector<int> findClosestElements(const std::vector<int>& arr, int k, int x) {
int left = std::lower_bound(arr.begin(), arr.end(), x) - arr.begin();
int right = left;
while (right - left < k) {
if (left == 0) ++right;
else if (right == (int)arr.size()) --left;
else if (x - arr[left-1] <= arr[right] - x) --left; // tie -> smaller
else ++right;
}
return std::vector<int>(arr.begin() + left, arr.begin() + right);
}Key points
- Binary search gives the start; the window expands toward the closer side.
<=breaks ties toward the smaller value.- The window stays contiguous, so the result is already sorted.
Contents
