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, 2016 at 8:48
  • $\begingroup$ Also see this answer, stackoverflow.com/a/7155426/948794 $\endgroup$
    – Makif
    Jul 30, 2016 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, 2016 at 9:31
  • 1
    $\begingroup$ @DavidRicherby Manhattan distance always means L1 distance. $\endgroup$
    – Yuval Filmus
    Jul 30, 2016 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, 2016 at 11:27

1 Answer 1

Reset to default
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, 2017 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.