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.
1def find_closest_elements(arr, k, x):
2 left, right = 0, len(arr) - k
3 while left < right:
4 mid = (left + right) // 2
5 if x - arr[mid] > arr[mid + k] - x:
6 left = mid + 1
7 else:
8 right = mid
9 return arr[left:left + k]We initiate a binary search between 0 and len(arr) - k. Depending on whether the element x is closer to the left or right side, we move the binary search mid-point. Once the position is found, the array is sliced from left to left + k to get the result.
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).
1def Using two pointers from both ends of the array, we check which value is closer to x and move the respective pointer inwards until only k elements are left. These k elements will be the closest to x.