Find k closest elements to a given value

Given a sorted array arr[] and a value X, find the k closest elements to X in arr[]. 

Examples: 

Input: K = 4, X = 35
       arr[] = {12, 16, 22, 30, 35, 39, 42, 
               45, 48, 50, 53, 55, 56}
Output: 30 39 42 45

Note that if the element is present in array, then it should not be in output, only the other closest elements are required.

In the following solutions, it is assumed that all elements of array are distinct.

A simple solution is to do linear search for k closest elements. 

1. Start from the first element and search for the crossover point (The point before which elements are smaller than or equal to X and after which elements are greater). This step takes O(n) time. 
2. Once we find the crossover point, we can compare elements on both sides of crossover point to print k closest elements. This step takes O(k) time.

The time complexity of the above solution is O(n).

An Optimized Solution is to find k elements in O(Logn + k) time. The idea is to use Binary Search to find the crossover point. Once we find index of crossover point, we can print k closest elements in O(k) time.  

39 30 42 45 

Time complexity: O(Logn + k).
Auxiliary Space: O(1), since no extra space has been used.

Approach 2: Using Priority Queue

This approach uses a priority queue (max heap) to maintain the k closest numbers to x. It iterates over the elements in the array and calculates their absolute differences from x. The pairs of absolute differences and negative values are pushed into the max heap. If the size of the max heap exceeds k, the element with the maximum absolute difference is removed. Finally, the top k elements from the max heap are extracted and stored in a result vector. The vector is then reversed to obtain the closest numbers in ascending order before being returned as the result.

Below is the implementation:

39 30 42 45 

Time Complexity: O(n log k), where n is the size of the array and k is the number of elements to be returned. The priority queue takes O(log k) time to insert an element and O(log k) time to remove the top element. Therefore, traversing through the array and inserting elements into the priority queue takes O(n log k) time. Popping elements from the priority queue and pushing them into the result vector takes O(k log k) time. Therefore, the total time complexity is O(n log k + k log k) which is equivalent to O(n log k).
Auxiliary Space: O(k), as we are using a priority queue of size k+1 and a vector of size k to store the result.

Exercise: Extend the optimized solution to work for duplicates also, i.e., to work for arrays where elements don’t have to be distinct.

Approach 3: Two Pointer Approach

Initialization:

• Initialize two pointers, left and right, pointing to the start and end of the array, respectively.

Binary Search:

• Use a binary search-like approach to narrow down the range until right – left >= k.
• Compare the absolute differences of the elements at left and right with the target.
• Move the pointers accordingly to minimize the absolute difference.

Print Result:

• Print the k closest elements within the narrowed down range.

30 35 39 42 

The time complexity of the above solution is O(n) and doesn’t require any extra space.

GeeksforGeeks

Improve