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.

  • 1
    $\begingroup$ It doesn't really matter for this question, but this "distance" is not a mathematical distance metric $\endgroup$
    – nir shahar
    Oct 9 at 15:58
  • $\begingroup$ 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! $\endgroup$
    – 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).

  • $\begingroup$ thanks a lot. It is helpful $\endgroup$ Oct 11 at 11:52

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.