Finding K closest elements from the median of an unsorted Array
Given an unsorted array, I am trying to find the K nearest elements to the median of an Array. I am having trouble finding the solution in linear running time.
A[] = 1, 2, 3, 4, 5 ,6 , 30 ,31, 32 ,33 ,34 # assume sorting part is done
Median here is 6.
Answer for this is 2,3,4,5,6.
Any help or hint will be appreciated.
1 answer

My suggestion for this would be a two step approach.
First, use the Median of Medians algorithm to find the Median of an unsorted array in linear time.
Second, scan the array and fill a Min Heap (of size k), where elements are organized according to distance to the median, in order to find the k nearest elements.
The above should have a runtime of O(N log(k)) which is linear in N.