Sponsored
Sponsored
This approach uses binary search to find the position where x would fit in the array or where it is located. From this point, a sliding window is expanded to the left and right to check k closest elements. Given the sorted nature of the array, this is efficient.
Time Complexity: O(log(n-k) + k) where n is the length of the array, and we are moving a window over it. Space Complexity: O(k) for storing the resulting subarray.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5vector<int> findClosestElements(vector<int>& arr, int k, int x) {
6 int left = 0, right = arr.size() - k;
7 while (left < right) {
8 int mid = (left + right) / 2;
9 if (x - arr[mid] > arr[mid + k] - x)
10 left = mid + 1;
11 else
12 right = mid;
13 }
14 return vector<int>(arr.begin() + left, arr.begin() + left + k);
15}Similar to Python's solution, the approach here uses C++ STL for a straightforward implementation. We perform a binary search to determine where to start collecting k elements, and use STL vector range to slice the elements.
This approach initiates two pointers from the start and end of the array and gradually closes inwards by comparing the distance from x from both ends until the closest k elements are left. This is linear after the search initialization.
Time Complexity: O(n). Space Complexity: O(k).
1def Using two pointers from both ends of the array, we check which value is closer to x and move the respective pointer inwards until only k elements are left. These k elements will be the closest to x.