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.
1import java.util.*;
2
3class Solution {
4 public List<Integer> findClosestElements(int[] arr, int k, int x) {
5 int left = 0, right = arr.length - k;
6 while (left < right) {
7 int mid = (left + right) / 2;
8 if (x - arr[mid] > arr[mid + k] - x)
9 left = mid + 1;
10 else
11 right = mid;
12 }
13 List<Integer> result = new ArrayList<>();
14 for (int i = left; i < left + k; ++i) {
15 result.add(arr[i]);
16 }
17 return result;
18 }
19}This is Java's implementation of the binary search approach. Arrays and ArrayList are utilized to handle subarray extraction post binary search index determination.
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.