Take the 2-minute tour ×

So the question is like this:

Given a location X and an array of locations, I want to get an array of locations that are closest to location X, in other words sorted by closest distance.

The way I solved this is by iterating through each location array and calculate the distance between X and that particular location, store that distance, and sort the location by distance using a Comparator. Done! Is there a better way to do this? Assuming that the sort is a merge sort, it should be O(n log n).

share|improve this question
The point here is to avoid doing O(n*log(n)) work each time X changes. –  n.m. Oct 30 '11 at 19:27
What's wrong with your current work? you like improve which part of your answer? –  Saeed Amiri Oct 30 '11 at 19:45
the interviewer asked can you do better, that's why I asked.. I like my solution –  xonegirlz Oct 30 '11 at 21:13
he probably wanted you to prove why you can't do better(there is a prove for lower bound complexity for sort algorithms it's O(n*logn)) –  Vladp Oct 30 '11 at 21:39
@xonegirlz my apologies - I definitely missed that you were storing the computed distance. –  Matt Ball Oct 31 '11 at 0:15
add comment

5 Answers

up vote 2 down vote accepted

If I understand this right, you can do this pretty quickly for multiple queries - as in, given several values of X, you wouldn't have to re-sort your solution array every time. Here's how you do it:

  1. Sort the array initially (O(n logn) - call this pre-processing)
  2. Now, on every query X, binary search the array for X (or closest number smaller than X). Maintain, two indices, i and j, one which points to the current location, one to the next. One among these is clearly the closest number to X on the list. Pick the smaller distance one and put it in your solution array. Now, if i was picked, decrement i - if j was picked, increment j. Repeat this process till all the numbers are in the solution array.

This takes O(n + logn) for each query with O(nlogn) preprocessing. Of course, if we were talking about just one X, this is not better at all.

share|improve this answer
add comment

The problem you describe sounds like a m-nearest neighbor search to me.

So, if I correctly understood your question, i.e. the notion of a location being a vector in a multidimensional metric space, and the distance being a proper metric in this space, then it would be nice to put the array of locations in a k-d-Tree. You have some overhead for the tree building once, but you get the search for O(log n) then.

A benefit of this, assuming you are just interested in the m < n closest available locations, you don't need to evaluate all n distances every time you search for a new X.

share|improve this answer
add comment

You should try using min-heap ds to implement this. Just keep on storing the locations in heap with key = diff of X and that location

share|improve this answer
the run time would be the same I assume, O (n log n)? Or would it be O(log n) –  xonegirlz Oct 30 '11 at 19:24
it will be O(nlogn) but it will avoid using additional space for storing diffs in separate DS. Although the point of storage is arguable :) –  saury Oct 30 '11 at 19:25
actually the diffs in my case is stored inside the Location class as well, so it doesn't cost a lot, just have an additional double inside the Location class to represent diffs –  xonegirlz Oct 30 '11 at 19:27
Thats why I said its arguable. And what you are doing already I think is the way to go :). However the problem may be solved more quickly if we know about the exact inputs of these locations. For example if we think that these location coordinates are going to be integer and are in limit between a and b (both not high) then we may like to use Radix sort of thing here. If the problem is more generic then your solution seems to be right thing to do –  saury Oct 30 '11 at 19:32
Yea, I don't think it's that detailed.. anyway thanks for the heap input sort, nice way of utilizing a ds –  xonegirlz Oct 30 '11 at 19:34
add comment

You can't do asymptotically better than O(n log n) if using a comparison-based sort. If you want to talk about micro-optimization of the code, though, some ideas include...

  1. Sort by squared distance; no reason to ever use sqrt() - sqrt() is expensive
  2. Only compute squared distance if necessary; if |dx1| <= |dx2| and |dy1| <= |dy2|, pt1 is closer than pt2 - integer multiplication is fast, but avoiding it in many cases may be somewhat faster

A thinking-outside-the-box solution might be to use e.g. Bucket sort... A linear time sorting algorithm which might be applicable here.

share|improve this answer
Yeah, but we are talking about 1D. (So there is no reason to square it at all.) –  muntoo Oct 30 '11 at 19:42
@muntoo: Really? Where does it say we can assume 1D? I only see "Location" being thrown around. –  Patrick87 Oct 30 '11 at 19:46
"Given a location X and an array of locations" we do not know what given.Y is, so we cannot really sort it if it were 2D. (given.X)^2 + (???)^2 = ??? –  muntoo Oct 30 '11 at 19:52
@muntoo: Oh, I see. So the fact that we're talking about a one-dimensional system is encoded by the use of X to denote the initial point. Naturally, in mathematics - and in programming, too - it's common to associate points and vectors in many different dimensional spaces with letters x, y and z. If the OP really means to limit the discussion to 1D space, though, I agree the thing about Euclidean distance isn't all that relevant. The question could have been a bit clearer on that point, however. –  Patrick87 Oct 30 '11 at 19:57
add comment

Proof by contradiction that you can't do better:

It is well known that comparison-based sorts are the only way to sort arbitrary numbers (which may include irrational numbers), and that they can't do better than n*log(n) time.

If you go through the list in O(n) time and select the smallest number, then use that as X, and somehow come up with a list of numbers that are sorted by distance to X, then you have sorted n numbers in less than O(n*log(n)) time.

share|improve this answer
add comment

Your Answer


