CareerCup

this can not be true

The idea is right that it should lie somewhere in between all these points. To do this we might do it like this sort the coordinates based on x coordinate and find the middle coordinate then sort the coordinates based in y coordinate and find the middle co ordinates one among these two should be the Point P. O(nlogn).

This solution is not right. Burden of proof is on the guy proposing the solution.

I doubt that the OP's solution is correct. Agreed that the proposer of the solution should offer a proof. This algorithm would be correct for a variant of this problem. Namely, if the distance metric were to be the Manhattan (street block, e.g. |x2 - x1| + |y2 - y1|) distance. I could prove that, but I'm not going to bother since that's not the question. Even then, this is only true when there's no requirement to pick any of the N points, but when you can pick any point on the grid.

@Eugene. In case of Manhattan, the solution would still be wrong.

In manhattan you need the median, not the mean.

By the way, was it expected that you beat O(n^2)? If your interviewer was asking this question just to see you write some code, maybe they just expected the straightforward O(n^2) approach.

True, even in the Manhattan version it would be the median and not the mean. I didn't pay very close attention when I read the proposed answer.

I think the above solution is right. Mean point by definition is a point whose sum of deviation from all the points is minimum and so from the given list, the point closest to the mean point is the answer.

No. Lookup Fermat point for the case of three points. That is not necessarily the median.

Now if you are given four points as three points A,B,C, and their fermat point D, then D is answer which is not the median.

Ridiculousness abounds on this site. People just make claims without any hint of trying to justify it.

Of course, a proof is still required to show that D, is not the closest point to the median :-)

The anonymous of Fermat point is right. The wiki has an example supporting his/her statement.

We can use the minimal length spanning tree concept. First to find minimal length to connect all the points on the coordinate then we can find a average point in them to to find minimum distance.

@Umesh: That doesn't make any sense to me. Want to explain further?

correction: unless we go for O(n^2) solution of course ))

ha, I think my answer is a little off, maybe a rolling mean would prove more useful. I saw the median has cases where it fails.

This will not work, consider having many values close to X2 and only one value for X1 and one value of X near the middle... The correct value would be one close to X2 since the sum of all their distances is minimal...

e.x. : x values: 1,15,30,31,32, 29, 33.... according to your method, source p should be ~17 --> (33+1)/2, where in actuality it will be closer to the median ~31 since the sum of all the distances to that point is minimal.

I recommend the above comment where the MEDIAN values of X and Y should be considered closest to the point

Rdo, you are right, the above solution works for even distribution of points. without any distant point from a cluster.

After you have a point (median x, median y) i suggest iterating out from the middle of the sorted x (or sorted y) list. Or iterate in from both ends, and keep track of the smallest distance... and that will be the point p. Run-time complexity: sort x= O(nlogn) sort y= O(nlogn) and finally iterate through = O(n/2) therefore overall complexity O(nlogn)

Can anyone comment on the correctness of the complexity analysis?

I would, but I need a more complete and more clear description of the algorithm.

I just took the analysis from sort(vector.begin(), vector.end()) being executed twice then doing a two pointer iteration to find the minimum distance in the array. basically:

sort x values in array, set median x
sort y values in array, set median y

set ptr1 to index 0 (doesn't matter what sorting the array is since we compare each value once)
set ptr2 to index n

iterate pointers ptr1++ and ptr2-- until they meet and just keep track of the minimum distance from point(median x, median y)

the min point is the answer

@rdo, I feel your answer correct

I feel...a disturbance in the force. Don't think about the answer, feeeeel the answer. :P

I'm just kidding. It's just the choice of "feel" when describing an answer is not the choice of words I'd use.

@rdo ... I cannot understand what are trying to do with the pointers .. are you calculating the min distance??

What i think is .. we had to find the point from where the distance is minimum to every other given point .. which should be the Median.

Please elaborate if you are doing anything else ?

That only works if the distance metric is Manhattan distance. Here it seems it's Euclidean distance.

I forgot to explain the calculation of median.

the median is the middle number of the list.

if the input is
(2,2)
(2,4)
(3,3)
(4,2)
(4,4)

then the calculation of the median can be done by making a list of x-axis and y-axis separately and sort them..
x-axis : 2,2,3,4,4
y-axis : 2,2,3,4,4

the median will be the middle of the two lists. i.e (3,3).