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 <stdlib.h>
2
3void merge(int* arr, int* aux, int left, int mid, int right) {
4 int i = left, j = mid + 1, k = left;
5 while (i <= mid && j <= right) {
6 if (abs(arr[i]) <= abs(arr[j]))
7 aux[k++] = arr[i++];
8 else
9 aux[k++] = arr[j++];
10 }
11 while (i <= mid) aux[k++] = arr[i++];
12 while (j <= right) aux[k++] = arr[j++];
13 for (i = left; i <= right; i++) arr[i] = aux[i];
14}
15
16void mergesort(int* arr, int* aux, int left, int right) {
17 if (left < right) {
18 int mid = left + (right - left) / 2;
19 mergesort(arr, aux, left, mid);
20 mergesort(arr, aux, mid + 1, right);
21 merge(arr, aux, left, mid, right);
22 }
23}
24
25int* findKClosestElements(int* arr, int arrSize, int k, int x, int* returnSize) {
26 int *aux = (int*)malloc(arrSize * sizeof(int));
27 for (int i = 0; i < arrSize; ++i)
28 arr[i] -= x;
29 mergesort(arr, aux, 0, arrSize - 1);
30 for (int i = 0; i < arrSize; ++i)
31 arr[i] += x;
32 *returnSize = k;
33 free(aux);
34 return arr;
35}The C solution does not follow the same binary approach due to limitations in expressive slicing. Here, a custom merge sort is applied (after transforming elements by subtracting x), and array subsecreasing is performed thereafter.
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).
1function The JavaScript program uses slice and a two-pointer approach to iterate from both ends inward until it identifies k elements close to x. The solution is efficient and optimal in handling the problem at hand.