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).
1using System;
2using System.Collections.Generic;
public class Solution {
public IList<int> FindClosestElements(int[] arr, int k, int x) {
int left = 0, right = arr.Length - 1;
while (right - left >= k) {
if (Math.Abs(arr[left] - x) > Math.Abs(arr[right] - x))
left++;
else
right--;
}
List<int> result = new List<int>();
for (int i = left; i <= right; ++i)
result.Add(arr[i]);
return result;
}
}The C# solution is based on a two-pointer approach. The method traps indices until they limit the scope to k closest elements. It efficiently reduces used space.