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? Can we solve it in O(1) space?
I got space limit exceeded there and can’t come with any better approach till now. Can anyone please help me to figure this out?