Print X array elements closest to the Kth smallest element in the array

Problem Statement:

Given two integers K, X, and an array arr[] consisting of N distinct elements, the task is to find X elements closest to the Kth smallest element from the given array.

Examples:

Input: arr[] = {1, 2, 3, 4, 10}, K = 3, X = 2
Output: 2 3
Explanation: Kth smallest element present in the given array is 3 and X(= 2) closest array elements to 3 are {2, 3} or {3, 4}.
Therefore, the required output is 2 3.

Input: arr[] = {1, 9, 8, 2, 7, 3, 6, 4, 5, 10, 13, 12, 16, 14, 11, 15}, K = 3, X = 5
Output: 1 2 3 4 5

Naive Approach: The simplest approach to solve this problem is to sort the array and print X closest elements to the Kth smallest element of the given array using the two-pointers technique.

Time Complexity: O(N * log N)
Auxiliary Space: O(1)

Efficient Approach: To optimize the above approach the idea is to efficiently compute the value of the Kth smallest element of the given array using the Median Selection Algorithm. Follow the steps below to solve the problem:

Algorithm:

Step 1: Calculate the Kth smallest, say KthElem of the given array using the Median Selection Algorithm.

Step 2: Initialize an array, say diff[] to store the absolute difference of arr[i] and KthElem.

• Create a map, say maps to map each element of the array to the absolute difference of the current element and KthElem.

Step 3: Traverse the given array and append arr[i] to maps[abs(KthElem — arr[i])].

Step 4: Calculate Xth smallest element, say XthElem of diff[] array using the Median Selection Algorithm to print exactly X closest items.

Step 5: Finally, traverse the diff[] array and check if XthElem less than or equal to diff[i] or not. If found to be true then print the element of the array with the help of maps.

Time Complexity: O(N )
Auxiliary Space: O(1)

Below is the code Snippet:

Thanks for Reading, DO hit a Clap if you liked it.

Happy Coding!