0
$\begingroup$

Given a sorted array A, the problem is to find a number that minimizes the sum of Manhattan distance to the numbers in the array. I found that the median of A is the solution, but was not able to come up for a proof or explanation for the same ( i.e why its not mean).

Any help is highly appreciated.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ math.stackexchange.com/questions/113270/… $\endgroup$ – Ariel Jul 30 '16 at 8:48
  • $\begingroup$ Also see this answer, stackoverflow.com/a/7155426/948794 $\endgroup$ – Makif Jul 30 '16 at 9:31
  • 2
    $\begingroup$ What does "Manhattan distance" mean in this context? What did you try? Where did you get stuck? $\endgroup$ – David Richerby Jul 30 '16 at 9:31
  • 1
    $\begingroup$ @DavidRicherby Manhattan distance always means L1 distance. $\endgroup$ – Yuval Filmus Jul 30 '16 at 9:35
  • $\begingroup$ There can easily be more than one "number that minimizes the sum of manhattan distance to all points". ​ For example, consider the sorted array [0,4]. ​ ​ ​ ​ $\endgroup$ – user12859 Jul 30 '16 at 11:27
1
$\begingroup$

marks the set of numbers P={P1,P2,P3,..,Pn}

need to find number X:

|P1-X|+|P2-X|+...+|Pn-X|=D, which minimizes D.

the fact that X is the median can be shown using induction on the number of numbers n in P.

Base: n=1: trivial to see that the median is P1 and |P1-P1|=D=0 is minimal (D>=0).

now suppose that this holds for all P of size |P|=n, we need to show that this holds for |P|=n+1.

In other words:

given that |P1-X|+|P2-X|+...+|Pn-X|=D is minimal when X=Pm is the median of P={P1,..,Pn} show that |P1-X|+|P2-X|+...+|Pn-X|=D is minimal when X=Pm' is the median of P={P1,..P(n+1)). notice that there are two cases m'=m+1 (n is even) or m'=m (n is odd).

I suggest drawing a simple example using n=3 and n+1=4 on an axis. Can you see why this must hold?

Improve this answer
$\endgroup$
1
  • $\begingroup$ I suggest learning LaTeX and using it to enhance the way your answers look. $\endgroup$ – Yuval Filmus Jan 27 '17 at 11:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.