Given $N$ pairs of points in the form $(x,y)$. How can we efficiently calculate the Manhattan distance between each pair of point?
One way is to simply calculate the distance between each pair of points, takes $\mathcal{O} (n^2)$ complexity.
Is there any other way to solve it?
I can give a hint, if we find the one with lowest $x$ coordinate $x_0$. (this can of course be done $O(n)$)
What information would we get if we did $|x-x_0|$ for all other $x$? (It would take $O(n)$ to do this also.)