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.
1function findClosestElements(arr, k, x) {
2 let left = 0, right = arr.length - k;
3 while (left < right) {
4 const mid = Math.floor((left + right) / 2);
5 if (x - arr[mid] > arr[mid + k] - x)
6 left = mid + 1;
7 else
8 right = mid;
9 }
10 return arr.slice(left, left + k);
11}The JavaScript implementation uses slice to extract the subarray after performing a binary search to identify where the k elements should start from.
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).
1#include <vector>
2#include <cstdlib> // for abs
using namespace std;
vector<int> findClosestElements(vector<int>& arr, int k, int x) {
int left = 0, right = arr.size() - 1;
while (right - left >= k) {
if (abs(arr[left] - x) > abs(arr[right] - x))
left++;
else
right--;
}
return vector<int>(arr.begin() + left, arr.begin() + right + 1);
}Similar to Python, this C++ approach closes in from both ends to leave only k closest elements using a two-pointer mechanism.