Hello all,

Can someone share their thoughts on the following question :

Given a array of n elements. You have to find the median of difference of pairs. For Example: Lets say the elements are {1,2,4,5}. So the pairs will be {(1,2),(1,4),(1,5),(2,4),(2,5),(4,5)}. The array formed by those pairs are {1,3,4,2,3,1}. So you have to find the median of this new array generated by the difference of pairs.

I know it can be easily done in O(n^2). Could anyone share their approach to solve it in less than O(n^2) time.

Thanks in advance.