Manhattan and Chebyshev Distance Tricks

This is an extension topic beyond most interviews; it pays off in OAs about points on a grid where the obvious O(n^2) pairwise scan is too slow, because one coordinate change turns Manhattan distance into something you can maximize in O(n).

Intuition

Three distances between points A = (x1, y1) and B = (x2, y2) come up:

• Euclidean: sqrt(dx^2 + dy^2). Compare squared distances to stay in integers.
• Manhattan: |dx| + |dy|, the number of steps when moving only horizontally and vertically (a taxi on a street grid, a rook moving one cell at a time on an empty board).
• Chebyshev: max(|dx|, |dy|), the number of king moves on a chessboard, since a diagonal step fixes both coordinates at once.

The key identity is

|dx| + |dy| = max(|dx + dy|, |dx - dy|)

(check the four sign cases). So if every point (x, y) is mapped to (u, v) = (x + y, x - y), the Manhattan distance between two points equals the Chebyshev distance between their images. Geometrically, the "diamond" of points at Manhattan distance 1 is a square rotated by 45 degrees, and the rotation turns it into the axis-aligned square of Chebyshev distance 1. The reverse map ((x + y) / 2, (x - y) / 2) turns Chebyshev into Manhattan.

Why it helps: Chebyshev distance is a maximum over coordinates, and a maximum of pairwise differences over a set of numbers is just max - min. So the largest Manhattan distance among n points is max(max u - min u, max v - min v), found in one pass.

Manhattan distance also separates by axis when you add it up: a sum of |dx| + |dy| terms is a sum over x plus a sum over y, so each axis can be optimized independently (medians, sorted prefix sums).

When to use it in interviews / OAs

• "Maximum Manhattan distance between any two points", or expressions like |a_i - a_j| + |b_i - b_j| + |i - j| (a Manhattan distance in three dimensions).
• "Meeting point minimizing the total walking distance on a grid": medians per axis.
• "Sum of Manhattan distances over all pairs": sort each axis and use prefix sums.
• Chess-king or 8-directional moves without obstacles: Chebyshev distance.
• "Remove one point to minimize the maximum distance": after the rotation only the extreme points matter.

Template

from itertools import product


def rotate(p):
    # (x, y) -> (x + y, x - y): Manhattan distance becomes Chebyshev distance
    x, y = p
    return x + y, x - y


def max_manhattan(points) -> int:
    us = [x + y for x, y in points]
    vs = [x - y for x, y in points]
    return max(max(us) - min(us), max(vs) - min(vs))


def max_manhattan_kd(points) -> int:
    # k dimensions: |d1| + ... + |dk| is the max over sign patterns of s1*d1 + ... + sk*dk
    k = len(points[0])
    best = 0
    for signs in product((1, -1), repeat=k - 1):  # fixing the first sign skips mirrored patterns
        proj = [p[0] + sum(s * c for s, c in zip(signs, p[1:])) for p in points]
        best = max(best, max(proj) - min(proj))
    return best

For each sign pattern, the projection s1*x1 + ... + sk*xk is a single number per point, and the largest difference of projections is max - min. Flipping all signs gives the same differences, which is why only 2^(k-1) patterns are needed.

Summing distances: one axis at a time

def best_meeting_total(points) -> int:
    # least total Manhattan distance from one meeting point to all points: a median per axis
    total = 0
    for axis in (0, 1):
        vals = sorted(p[axis] for p in points)
        med = vals[len(vals) // 2]
        total += sum(abs(v - med) for v in vals)
    return total


def sum_pairwise_manhattan(points) -> int:
    # per axis, after sorting, value v at index i exceeds each of the i values before it
    total = 0
    for axis in (0, 1):
        prefix = 0
        for i, v in enumerate(sorted(p[axis] for p in points)):
            total += v * i - prefix
            prefix += v
    return total


def king_moves(s, t) -> int:
    return max(abs(s[0] - t[0]), abs(s[1] - t[1]))  # Chebyshev distance


def grid_steps(s, t) -> int:
    return abs(s[0] - t[0]) + abs(s[1] - t[1])  # Manhattan distance

The median minimizes a sum of absolute deviations: moving the meeting coordinate past the median increases the distance to more points than it decreases. With an even count, any value between the two middle elements is optimal.

Complexity

Maximum Manhattan distance: O(n) in 2D, O(2^(k-1) * k * n) in k dimensions. Best meeting point and pairwise sums: O(n log n) for the sorts. King moves and grid steps: O(1).

Common pitfalls

• Using only one of the rotated coordinates: the maximum can come from u = x + y or from v = x - y; check both.
• Going back from Chebyshev to Manhattan: the reverse map divides by 2. Multiply all coordinates by 2 first, or remember that u and v always have the same parity.
• Obstacles: Manhattan and Chebyshev distances are shortest paths only on empty grids; with walls you need BFS.
• Euclidean comparisons with floats: compare dx*dx + dy*dy instead of square roots.
• Overflow: with 10^5 points and coordinates up to 10^9, the sum over all pairs can reach about 10^19, just past the signed 64-bit range. In C++/Java take the modulo the problem asks for, or use a wider accumulator.

Interview variations

• Maximum of an absolute-value expression over pairs of indices: treat each index as a point in 3D Manhattan space.
• Best meeting point on a grid: medians of rows and columns.
• Minimize Manhattan distances after removing one point: compute extremes of x + y and x - y, then try removing each extreme point.
• Minimum time to visit points in order when diagonal moves are allowed: sum of Chebyshev distances.
• Sum of distances between all pairs of grid points or of numbers on a line: sorting plus prefix sums.
• Connect all points with minimum Manhattan cost: a minimum spanning tree over the complete graph (Prim in O(n^2) for moderate n).