I have a list. I have to find median of absolute difference of all pairs of array.

Eg - A={1,2,10}

Difference for all distinct pairs :




The new list is A'=[8,8,9] and the median is 8.

Now I took all the pairs and made a list with difference of them and median is A'.length()/2th element i.e. 8.

But is there a way to do without taking all the pairs as the time complexity is O(n2) and I want to reduce the time complexity to O(nlogn) or less.

  • $\begingroup$ That's a nice (and challenging) exercise. We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Feb 3 '18 at 18:36
  • $\begingroup$ To give you something to start with, show that given a difference $D$, you can determine its index in the absolute difference array in time $O(n\log n)$. $\endgroup$ – Yuval Filmus Feb 4 '18 at 10:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.