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.
Sort and Binary search on the answer. For checking if x is possible during binary search, make a function check(x) that does the following: For each index i, finds the first index j such that a[j]-a[i]>x. You will have j-i-1 pairs in the difference array corresponding to this such that the differences are <= x. Add these counts for all i and finally if the count in the check(x) function is =(N/2)-1 you're done.
But how does it have monotonicity? I mean its possible that x is not possible just because its not a valid difference pair of the two array values.
I think you mean to say 'How do we know the binary searched value exists exactly' Well, Since we are checking for the minimum element with Rank N/2, notice that if the answer is X and we are checking for X-h, then the Rank will be N/2-1 so it will be ignored. If it is X+h, it will be >= N/2 but since we are looking for that minimum value of h, it will always manage to give answer X.