swordx's blog

Median of difference of pairs

By swordx, history, 6 years ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply