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.

  • 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$ Jul 30, 2016 at 9:31
  • 1
    $\begingroup$ @DavidRicherby Manhattan distance always means L1 distance. $\endgroup$ 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


marks the set of numbers $$P=\{P_1,P_2,P_3, \ldots ,P_n\}$$

need to find number $X$:

$|P_1-X|+|P_2-X|+\ldots+|P_n-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 $P_1$ and $|P_1-P_1|=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 $$|P_1-X|+|P_2-X|+\ldots+|P_n-X|=D$$ is minimal when $X=P_m$ is the median of $P=\{P_1,P_2,P_3, \ldots ,P_n\}$ show that $|P_1-X|+|P_2-X|+\ldots+|P_n-X|=D$ is minimal when $X=P_m'$ is the median of $P=\{P_1,P_2,P_3, \ldots ,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?

  • $\begingroup$ I suggest learning LaTeX and using it to enhance the way your answers look. $\endgroup$ Jan 27, 2017 at 11:39
  • $\begingroup$ Is this a question or an answer? $\endgroup$
    – rosshjb
    Jan 26 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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