# Given an array of n points of the form (x,y), the distance between two points (x1,y1) and (x2,y2) is defined as min(abs(x1-x2), abs(y1-y2))

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.

• It doesn't really matter for this question, but this "distance" is not a mathematical distance metric Oct 9 at 15:58
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– D.W.
Oct 10 at 6:42

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).