I have a list. I have to find median of absolute difference of all pairs of array.
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.