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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<int> FindClosestElements(int[] arr, int k, int x) {
6 int left = 0, right = arr.Length - 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 List<int> result = new List<int>();
15 for (int i = left; i < left + k; ++i) {
16 result.Add(arr[i]);
17 }
18 return result;
19 }
20}The C# version is similar to Java and uses a List to return the result after employing a binary search to determine the start of k 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.