Maximum Manhattan distance in a set of points

Given a set of points on a 2D plane, the greatest Manhattan distance between any two points can be found in 1 pass, linear time, and constant space.

Time Complexity: O(N), where N is the number of points

Space Complexity: O(1)

Code

Given:

min_sum = float('inf')
max_sum = float('-inf')
min_diff = float('inf')
max_diff = float('-inf')

# If you are not interested in the points themselves, you can remove these variables
min_sum_i = -1
max_sum_i = -1
min_diff_i = -1
max_diff_i = -1

for i in range(len(points)):
    x, y = points[i]

    if x + y > max_sum:
        max_sum = x + y
        max_sum_i = i

    if x + y < min_sum:
        min_sum = x + y
        min_sum_i = i

    if x - y > max_diff:
        max_diff = x - y
        max_diff_i = i
    
    if x - y < min_diff:
        min_diff = x - y
        min_diff_i = i

if max_sum - min_sum > max_diff - min_diff:
    # Points indices = [max_sum_i, min_sum_i]
    return max_sum - min_sum
else:
    # Points indices = [max_diff_i, min_diff_i]
    return max_diff - min_diff

Explanation

The formula for Manhattan distance is:

Manhattan(Pi,Pj)=∣xi−xj∣ + ∣yi−yj∣\mathrm{Manhattan} \lparen P_i , P_j \rparen = \lvert x_i - x_j \lvert \, + \, \lvert y_i - y_j \lvert
First, let's remove the absolute value bars from the formula. This will give us the following four equations:
={xi−xj+yi−yjif xi≥xj and yi≥yjxi−xj−yi+yjif xi≥xj and yi<yj−xi+xj+yi−yjif xi<xj and yi≥yj−xi+xj−yi+yjif xi<xj and yi<yj= \begin{cases} x_i - x_j + y_i - y_j &\text{if } x_i \ge x_j \text{ and } y_i \ge y_j \\ x_i - x_j - y_i + y_j &\text{if } x_i \ge x_j \text{ and } y_i \lt y_j \\ -x_i + x_j + y_i - y_j &\text{if } x_i \lt x_j \text{ and } y_i \ge y_j \\ -x_i + x_j - y_i + y_j &\text{if } x_i \lt x_j \text{ and } y_i \lt y_j \end{cases}
Now, we will group together the corresponding X and Y values for each point:
={xi+yi−xj−yjif xi≥xj and yi≥yjxi−yi−xj+yjif xi≥xj and yi<yj−xi+yi+xj−yjif xi<xj and yi≥yj−xi−yi+xj+yjif xi<xj and yi<yj= \begin{cases} x_i + y_i - x_j - y_j &\text{if } x_i \ge x_j \text{ and } y_i \ge y_j \\ x_i - y_i - x_j + y_j &\text{if } x_i \ge x_j \text{ and } y_i \lt y_j \\ -x_i + y_i + x_j - y_j &\text{if } x_i \lt x_j \text{ and } y_i \ge y_j \\ -x_i - y_i + x_j + y_j &\text{if } x_i \lt x_j \text{ and } y_i \lt y_j \end{cases}
Pull out some minus signs:
={(xi+yi)−(xj+yj)if xi≥xj and yi≥yj(xi−yi)−(xj−yj)if xi≥xj and yi<yj−(xi−yi)+(xj−yj)if xi<xj and yi≥yj−(xi+yi)+(xj+yj)if xi<xj and yi<yj= \begin{cases} (x_i + y_i) - (x_j + y_j) &\text{if } x_i \ge x_j \text{ and } y_i \ge y_j \\ (x_i - y_i) - (x_j - y_j) &\text{if } x_i \ge x_j \text{ and } y_i \lt y_j \\ -(x_i - y_i) + (x_j - y_j) &\text{if } x_i \lt x_j \text{ and } y_i \ge y_j \\ -(x_i + y_i) + (x_j + y_j) &\text{if } x_i \lt x_j \text{ and } y_i \lt y_j \end{cases}
We can define two variables as follows:
sumi=si=xi+yidiffi=di=xi−yi\mathrm{sum}_i = s_i = x_i + y_i \newline \mathrm{diff}_i = d_i = x_i - y_i
And rewrite our equations:
={si−sjif xi≥xj and yi≥yjdi−djif xi≥xj and yi<yj−di+djif xi<xj and yi≥yj−si+sjif xi<xj and yi<yj= \begin{cases} s_i - s_j &\text{if } x_i \ge x_j \text{ and } y_i \ge y_j \\ d_i - d_j &\text{if } x_i \ge x_j \text{ and } y_i \lt y_j \\ -d_i + d_j &\text{if } x_i \lt x_j \text{ and } y_i \ge y_j \\ -s_i + s_j &\text{if } x_i \lt x_j \text{ and } y_i \lt y_j \end{cases}
Notice that which point is 'i' and which is 'j' is arbitrary, since we are only interested in the specific i and j combination resulting in the greatest distance.
Therefore, -si + sj is functionally equivalent to si - sj. This means that we are just interested in finding the maximum of:
={si−sjdi−dj= \begin{cases} s_i - s_j \\ d_i - d_j \end{cases}
Therefore:
maxi,jManhattan(Pi,Pj)=maxi,j(max(si−sj,di−dj))\underset{i, j}{\mathrm{max}} \mathrm{Manhattan} \lparen P_i , P_j \rparen = \underset{i, j}{\mathrm{max}} \lparen \mathrm{max} \lparen s_i - s_j , d_i - d_j \rparen \rparen
In order to maximize these values, we need the largest si and di, and the smallest sj and dj. This is why we use 4 variables to track the max and min x + y and x - y in the code.
maxi,jManhattan(Pi,Pj)=max(summax−summin,diffmax−diffmin)\underset{i, j}{\mathrm{max}} \mathrm{Manhattan} \lparen P_i , P_j \rparen = \mathrm{max} \lparen \mathrm{sum}_{max} - \mathrm{sum}_{min} , \mathrm{diff}_{max} - \mathrm{diff}_{min} \rparen

These equations were sourced from a post by Shivam Aggarwal.

Example Problems