I need to find the point that will minimise the sum of Manhattan distances from a list of points. so given a list lets say [[x0, y0], [x1, y1] ...] (not sorted) I have to find the point to minimise the manhattan distance from that list of points. I understand the question but am having trouble with how i can complete this in O(n) time.

CodePudding user response：

You can find the median of a list of numbers in linear time.

Taking the x-coordinates and y-coordinates separately, find the median of each. If you need integer coordinates, round half-values to the nearest integer.

The distance minimizing point (DMP) is (median of x-values, median of y-values). There may be multiple DMPs, but this will be one of them.

Why? Well, along either axis, if there are more points in one direction than the other, say p to the left and q to the right, p < q, then moving 1 to the right will increase the distance to p points by 1 and reduce the distance to q points by 1, so reduce the sum of Manhattan distances to points by q-p.