Find k Closest Elements
Given a sorted array, this algorithm returns the k elements closest to a target value x. The output is sorted in ascending order.
Steps
- We apply binary search to find the best starting index of the k closest elements window.
- We compare
arr[m + k] - xandx - arr[m]to decide whether to shift the window left or right. - Once we find the optimal window, return the subarray from index
ltol + k - 1.
Dry Run
Input: [1, 2, 3, 4, 5], k = 4, x = 3
Output: [1, 2, 3, 4]
Input: [1, 1, 2, 3, 4, 5], k = 4, x = -1
Output: [1, 1, 2, 3]
Time & Space Complexity
- Time: O(log(n – k) + k)
- Space: O(k)
var findClosestElements = function(arr, k, x) {
let l = 0;
let r = arr.length - k;
while (l < r) {
let m = l + Math.floor((r - l) / 2);
if ((arr[m + k] - x) < (x - arr[m])) {
l = m + 1;
} else {
r = m;
}
}
let ans = [];
for(let i = l; i < l + k; i++) {
ans.push(arr[i]);
}
return ans;
};
vector findClosestElements(vector& arr, int k, int x) {
int l = 0, r = arr.size() - k;
while (l < r) {
int m = l + (r - l) / 2;
if (x - arr[m] > arr[m + k] - x) {
l = m + 1;
} else {
r = m;
}
}
return vector(arr.begin() + l, arr.begin() + l + k);
}
int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
int l = 0, r = arrSize - k;
while (l < r) {
int m = l + (r - l) / 2;
if (x - arr[m] > arr[m + k] - x)
l = m + 1;
else
r = m;
}
int* res = (int*)malloc(k * sizeof(int));
for (int i = 0; i < k; ++i)
res[i] = arr[l + i];
*returnSize = k;
return res;
}
public List findClosestElements(int[] arr, int k, int x) {
int l = 0, r = arr.length - k;
while (l < r) {
int m = l + (r - l) / 2;
if (x - arr[m] > arr[m + k] - x)
l = m + 1;
else
r = m;
}
List res = new ArrayList<>();
for (int i = l; i < l + k; i++)
res.add(arr[i]);
return res;
}
def findClosestElements(arr, k, x):
l, r = 0, len(arr) - k
while l < r:
m = l + (r - l) // 2
if x - arr[m] > arr[m + k] - x:
l = m + 1
else:
r = m
return arr[l:l + k]
public IList FindClosestElements(int[] arr, int k, int x) {
int l = 0, r = arr.Length - k;
while (l < r) {
int m = l + (r - l) / 2;
if (x - arr[m] > arr[m + k] - x)
l = m + 1;
else
r = m;
}
List result = new List();
for (int i = l; i < l + k; i++)
result.Add(arr[i]);
return result;
}
