Find K Closest Elements
You are given a sorted array 'A' of length 'N', two integers 'K' and 'X'. Your task is to print 'K' integers closest to 'X', if two integers are at the same distance return the smaller one.

The output should also be in sorted order

Note:

An integer 'a' is closer to 'X' than an integer 'b' if: |a - X|

Question

Find K Closest Elements

You are given a sorted array 'A' of length 'N', two integers 'K' and 'X'. Your task is to print 'K' integers closest to 'X', if two integers are at the same distance return the smaller one.

The output should also be in sorted order

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 )

For Example:

if X = 4,  3 is closer to 'X' than 9, as |3-4| < |9-4|  i.e., 1 < 5   and if X = 4, 2 and 6 are equally close to it, as |2-4| == |6-4| = 2, but we say 2 is closer to 4 than 6, as 2 is smaller.

Input Format:

The first line of the input contains ‘T’ denoting the number of test cases.

The first line of each test case contains the three integers 'N', 'K', and 'X'.

The second line of each test case contains 'N' space-separated integers of the array 'A'.

Output Format:

Return the k space-separated integers.

The output of each test case is printed on a new line.

Constraints:

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

Time Limit: 1 second

Accepted Answer

I proposed the following solution -
Perform a binary search on distance. In each iteration of the binary search, check how many pairs have a distance less than mid and then update low and high bounds in accordance with K.

Accepted Answer

Sort After Taking the Difference

Explanation:

The key idea is to sort the array using comparator where elements are compared based on the condition: |a - X| < |b - X| or ( |a - X| == |b - X| and a < b ), where ‘a’ and ‘b’ are two integers in the array.
Then pick the 'K' smallest elements from this new sorted array and add them into a new array.
Then sort this new array of size 'K', and return it.

Algorithm:

Sort the array using conditions, i.e., compare two integers in it by taking its absolute difference with 'X'. and then taking the smaller one first.
Make a list of the first ‘K’ elements and sort them.
Return this list of 'K' elements.

Space Complexity: O(n)Explanation:

O(K), Where 'K' is the length of the output array.

We are creating a new list of ‘K’ elements therefore, space complexity is O(K).

Time Complexity: O(nlogn)Explanation:

O( N*log(N) ), Where ‘N’ is the length of the array

We are sorting the array which takes O(N * log(N)) time.

Java (SE 1.8)

/*

    Time Complexity     :   O(N * log(N))

    Space Complexity    :   O(K)



    Where 'N' is length of the input array and 'K' is the length of the output array.

*/



import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;



public class Solution {

    public static ArrayList kClosest(ArrayList a, int n, int k, int x) {

		// Sort 'a' as per the condition.

        Collections.sort(a, new Comparator(){

			public int compare(Integer x1, Integer x2) {

				if (Math.abs(x1 - x) == Math.abs(x2 - x)) {

					return x1 - x2;

				}

				return Math.abs(x1 - x) - Math.abs(x2 - x);

			}

			

		});



		ArrayList newArray = new ArrayList<>();

		for (int i = 0; i < k; i++) {

			newArray.add(a.get(i));

		}



		// Sort the first 'K' elements, as they may not be in order.

		Collections.sort(newArray);



		return newArray;

    }

}

Python (3.5)

"""

    Time Complexity     :   O(N * log(N))

    Space Complexity    :   O(K)



    Where 'N' is length of the input array and 'K' is the length of the output array.

"""



def KClosest(a, n, k, x):

    # Sort 'a' as per the condition.

    a.sort(key = lambda y : abs(y - x))

    

    newArray = a[0 : k]



    # Sort the first 'K' elements, as they may not be in order.

    newArray.sort()



    return newArray

C++ (g++ 5.4)

/*

    Time Complexity     :   O(N * log(N))

    Space Complexity    :   O(K)



    Where 'N' is length of the input array and 'K' is the length of the output array.

*/



#include 



int X;



// This function describes how should we compare two elements while sorting.

bool compare(int x1, int x2) {

	if (abs(x1 - X) == abs(x2 - X)) {

		return x1 < x2;

	}

	return abs(x1 - X) < abs(x2 - X);

}



vector KClosest(vector &a, int n, int k, int x) {

	X = x;



	// Sort 'a' as per the condition.

	sort(a.begin(), a.end(), compare);



	vector newArray;

	for (int i = 0; i < k; i++) {

		newArray.push_back(a[i]);

	}



	// Sort the first 'K' elements, as they may not be in order.

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



	return newArray;

}

Accepted Answer

Binary Search

The key idea is that we know that the final answer will be some contiguous sequence in array ‘A’. So we initially take the complete array as our answer then reduce its range.

Algorithm:

Initially let ‘low' = 0 and ‘high’ = N - 1, Where ‘low’ and ‘high’ tell the range of integers taken in the final answer.
If at any point (high - low + 1) = K, i.e., the size of the range is ‘K’, that range of integers is the answer. And we create a new array of that range and return it.
If not, then we check if which one of ‘A[low]’ and ‘A[high]’ is at a smaller distance from ‘X’, whoever is at a smaller distance we keep it, and remove the other.
If ‘low’ is at a smaller distance, we decrement ‘high’, i.e., high = high - 1.
If ‘high’ is at a smaller distance, we increment ‘low’, i.e., low = low + 1.

Space Complexity: OtherExplanation:

O(K), Where ‘K’ is the length of the new array.

We are creating a new list of ‘K’ elements therefore, space complexity is O(K)

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ is the length of the array.

In the worst case, we will only be traversing the array once thus time complexity is O(N).

Java (SE 1.8)

/*

    Time Complexity     :   O(N)

    Space Complexity    :   O(N)



    Where 'N' is length of the input array.

*/



import java.util.ArrayList;



public class Solution {

    public static ArrayList kClosest(ArrayList a, int n, int k, int x) {

		int low = 0, high = n - 1;



		while (high - low + 1 > k) {

			if (Math.abs(a.get(low) - x) <= Math.abs(a.get(high) - x)) {

				high--;

			} else {

				low++;

			}

		}



		ArrayList ans = new ArrayList<>();

		for (int i = low; i <= high; i++) {

			ans.add(a.get(i));

		}



		return ans;

    }

}

C++ (g++ 5.4)

/*

    Time Complexity     :   O(N)

    Space Complexity    :   O(N)



    Where 'N' is length of the input array.

*/



vector KClosest(vector &a, int n, int k, int x) {

	int low = 0, high = n - 1;



	while (high - low + 1 > k) {

		if (abs(a[low] - x) <= abs(a[high] - x)) {

			high--;

		} else {

			low++;

		}

	}



	vector ans;

	for (int i = low; i <= high; i++) {

		ans.push_back(a[i]);

	}



	return ans;

}

Python (3.5)

"""

    Time Complexity     :   O(N)

    Space Complexity    :   O(N)



    Where 'N' is length of the input array.

"""



def KClosest(a, n, k, x):

    low = 0

    high = n-1



    while(high - low + 1 > k):

        if(abs(a[low] - x) <= abs(a[high] - x)):

            high -= 1

        else:

            low += 1



    ans = []



    for i in range(low, high+1):

        ans.append(a[i])



    return ans

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;

}