We need to find mth smallest possible distance by considering all possible pairs. I solved this problem by considering all possible pairs and maintaining a max priority queue. If the max priority queue size is less than m I push the current distance into it. Otherwise, if the size of the priority queue is greater than equal to m I check whether top of priority queue is greater than it. If so, I pop it and push this distance. The time complexity of this solution seems to be O(N^2 logn) while space complexity O(m). Can we do better than this? Especially can we do this in O(1) extra space.
There is a $O(n \log n)$ solution by divide and conquer, see for example here for Euclidean distances (shouldn't make much of a difference for this problem).