# Proof that median of an array is the number that minimizes the sum of manhattan distance to all points

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.

• math.stackexchange.com/questions/113270/… Jul 30 '16 at 8:48
• Also see this answer, stackoverflow.com/a/7155426/948794 Jul 30 '16 at 9:31
• What does "Manhattan distance" mean in this context? What did you try? Where did you get stuck? Jul 30 '16 at 9:31
• @DavidRicherby Manhattan distance always means L1 distance. Jul 30 '16 at 9:35
• 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]. ​ ​ ​ ​
– user12859
Jul 30 '16 at 11:27

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?

• I suggest learning LaTeX and using it to enhance the way your answers look. Jan 27 '17 at 11:39