Find K Closest Elements

Given a sorted array 'A' of length 'N', and two integers 'K' and 'X', your task is to find 'K' integers from the array closest to 'X'. If two integers are at the same distance, prefer the smaller one.

Input:

T N K X A[0] A[1] ... A[N-1]

Output:

B[0] B[1] ... B[K-1]

Example:

Input:

1 8 3 5 1 2 3 4 5 6 7 8

Output:

4 5 6

Constraints:

1

Question

Find K Closest Elements

Given a sorted array 'A' of length 'N', and two integers 'K' and 'X', your task is to find 'K' integers from the array closest to 'X'. If two integers are at the same distance, prefer the smaller one.

Input:

T 
N K X 
A[0] A[1] ... A[N-1]

Output:

B[0] B[1] ... B[K-1]

Example:

Input:

1 
8 3 5 
1 2 3 4 5 6 7 8

Output:

4 5 6

Constraints:

1 <= T <= 5
1 <= N, K <= 5000
1 <= A[i], X <= 10^6

Note:

An integer 'a' is closer to 'X' than an integer 'b' if: |a - X| < |b - X| or (|a - X| == |b - X| and a < b).

Accepted Answer

Find K closest elements to X in a sorted array A.

Use binary search to find the closest element to X in the array.
Maintain two pointers to expand around the closest element to find K closest elements.
Handle cases where two elements are equidistant by choosing the smaller one.
Return the K closest elements in a new array.

Accepted Answer

Hope this C++ code will help you :)

#define pair pair class cmp{ public: bool operator()(pair a, pair b){ if(a.first!=b.first)return a.first>b.first; return a.second>b.second; } }; class Solution { public: vector findClosestElements(vector& arr, int k, int x) { priority_queue,cmp> pq; for(int i=0;i ans; while(!pq.empty()&&ans.size()

Accepted Answer

vector closestelements(vector &a , int k , int x){

int left=0;

int right=a.size()-1;

while(left

int mid = left + (right - left) / 2;

if (A[mid] == X) { left = mid; break;

} else if (A[mid] < X) {

left = mid + 1;

} else {

right = mid - 1;

}

vector result;

int l = left - 1;

int r = left;

while (K > 0) {

if (l >= 0 && r < A.size()) {

if (abs(A[l] - X) <= abs(A[r] - X)) {

result.push_back(A[l]); l--;

}

else {

result.push_back(A[r]); r++;

}

else if (l >= 0) {

result.push_back(A[l]); l--;

} else if (r < A.size()) {

result.push_back(A[r]);

r++;

}

K--;

}

sort(result.begin(), result.end());

return result;

}

Asked in Trilogy Innovations