Given the constraints of this problem (n <= 1E6), how can we solve this problem?
The naive brute force solution( O(n^2) ) checking all pairwise distances will fail. Any ideas will be appreciated.
Need personalized 1-on-1 mentorship? 
Upgrade to CommonLounge Plus for text-based one on one mentorship that includes code reviews, feedback on projects, career counseling and much more.