Find K Closest Elements

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
18 upvotes
Asked in companies
AmazonMorgan StanleyOptum

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5 4 3
1 2 3 4 5
5 5 -1
1 2 3 4 5
Sample Output 1:
1 2 3 4
1 2 3 4 5
Explanation For Sample Output 1:
For test case 1:

Subtracting 'X' from all elements of A, and taking the absolute value we get : [2 1 0 1 2]

From this array, we have to pick the 4 smallest numbers, which are A[1], A[2], A[3], and either of A[0] and A[4] as both are at the same distance.

But since A[0] < A[4] (1 < 4) we pick A[0] (1).

Therefore the answer is [ A[0], A[1], A[2], A[3] ] or [1 2 3 4]

For test case 2:
We take all 5 elements as it demands 5 elements.
Therefore, the answer is [1 2 3 4 5]
Sample Input 2:
2
10 5 30
1 6 9 15 20 26 31 36 39 42 
9 1 6
1 1 1 4 5 6 8 9 9
Sample Output 2:
20 26 31 36 39 
6
Hint

Sort the array after taking the difference.

Approaches (2)
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.
Time Complexity

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

 

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

Space Complexity

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).

Code Solution
(100% EXP penalty)
Find K Closest Elements
Full screen
Console