LeetCode 3102: Minimize Manhattan Distances

Exclude each point

We can find the max distance between pairs of points excluding each point and take the minimum.

Time: $\mathcal{O}(n^3)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def max_distance_without(self, excluded, points):
        def manhattan_distance(a, b):
            return abs(a[0]-b[0]) + abs(a[1]-b[1])

        max_distance = 0
        for i in range(len(points)):
            if i == excluded:
                continue
            for j in range(i+1, len(points)):
                if j == excluded:
                    continue
                
                max_distance = max( max_distance, manhattan_distance( points[i], points[j] ) )

        return max_distance 

    def minimumDistance(self, points: List[List[int]]) -> int:
        min_distance = float("inf")
        for excluded in range(len(points)):
            min_distance = min( min_distance, self.max_distance_without(excluded, points) )
        
        return min_distance

Extreme points

We want to remove one of the “extreme points” because extreme points are the furthest apart from each other.

Say we have a pair of points: $\langle P_i(x_i, y_i), P_j(x_j, y_j) \rangle$ . The Manhattan distance between the pair of points: $M(P_i, P_j) = |x_i - x_j| + |y_i - y_j|$ . To find the pair of points that are furthest apart from each other, we cannot just look at the distance in one of the coordinates. Because, the pair of points furthest apart in x-coordinate might be very close in y-coordinate. So, we reformulate the Manhattan distance using an alternative definition of absolute value. The reformulation casts the points in a different coordinate system where, we can find the the pair of points furthest apart from each other by looking at one coordinate at a time.

The usual definition of the absolute value function is:

$|a| = \begin{cases} a, & \text{if } a \ge 0 \\ -a & \text{otherwise} \end{cases}$

Alternatively, we can also write:

$|a| = \max{(a, -a)}$ .

With the alternative definition of absolute value function, the Manhattan distance becomes:

$M(P_i, P_j) = \max{ \left( (x_i-x_j), -(x_i-x_j) \right) } + \max{ \left( (y_i - y_j), -(y_i - y_j) \right) }$

We have two choices for the first $\texttt{max}$ and two choices for the second $\texttt{max}$ . So, the Manhattan distance is the maximum among four possible values:

$M(P_i, P_j) = \max{ \left( (x_i-x_j)+(y_i-y_j), (x_i-x_j)+(-(y_i-y_j)), -(x_i-x_j)+(y_i-y_j), -(x_i-x_j)+(-(y_i-y_j)) \right) }$

We can rearrange the terms to get:

$M(P_i, P_j) = \max{ \left( (x_i+y_i)-(x_j+y_j), -[(x_i+y_i)-(x_j+y_j)], (x_i-y_i)-(x_j-y_j), -[(x_i-y_i)-(x_j-y_j)] \right) }$

All four terms now involve sum or difference between a point’s coordinates. Say $\sigma_i = x_i + y_i$ and $\delta_i = x_i-y_i$ . So, $\sigma_i$ and $\delta_i$ are the two coordinates of the point $P_i$ in the new coodinate system.

$M(P_i, P_j) = \max{ \left( \sigma_i - \sigma_j, -(\sigma_i - \sigma_j), \delta_i - \delta_j, -(\delta_i - \delta_j) \right) } = \max{ \left( \max{ \left( \sigma_i-\sigma_j, -(\sigma_i-\sigma_j) \right) }, \max{\left( \delta_i-\delta_j, -(\delta_i-\delta_j) \right)} \right) }$

Finally, $M(P_i, P_j) = \max{ \left( |\sigma_i-\sigma_j|, | \delta_i - \delta_j | \right) }$ .

The extreme points for the Manhattan distance are the points having $\sigma_{\text{max}}, \sigma_{\text{min}}, \delta_{\text{max}}, \delta_{\text{min}}$ . We should remove one of these four points. To find the distance after removing one of these points, we also keep track of $\sigma_{\text{max}}^{\text{2nd}}, \sigma_{\text{min}}^{\text{2nd}}, \delta_{\text{max}}^{\text{2nd}}, \delta_{\text{min}}^{\text{2nd}}$ .

Time: $\mathcal{O}(n)$ , space: $\mathcal{O}(1)$ .

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        sum_max = sum_max2 = diff_max = diff_max2 = float("-inf")
        sum_max_i = diff_max_i = None
        sum_min = sum_min2 = diff_min = diff_min2 = float("inf")
        sum_min_i = diff_min_i = None

        for i, p in enumerate(points):
            x, y = p

            sum = x + y
            if sum > sum_max:
                sum_max, sum_max2 = sum, sum_max
                sum_max_i = i
            elif sum > sum_max2:
                sum_max2 = sum

            if sum < sum_min:
                sum_min, sum_min2 = sum, sum_min
                sum_min_i = i
            elif sum < sum_min2:
                sum_min2 = sum

            diff = x - y
            if diff > diff_max:
                diff_max, diff_max2 = diff, diff_max
                diff_max_i = i
            elif diff > diff_max2:
                diff_max2 = diff

            if diff < diff_min:
                diff_min, diff_min2 = diff, diff_min
                diff_min_i = i
            elif diff < diff_min2:
                diff_min2 = diff

        min_dist_removed = float("inf")
        for removed_i in (sum_max_i, sum_min_i, diff_max_i, diff_min_i):
            max_sum_removed = sum_max2 if removed_i == sum_max_i else sum_max
            min_sum_removed = sum_min2 if removed_i == sum_min_i else sum_min
            max_diff_removed = diff_max2 if removed_i == diff_max_i else diff_max
            min_diff_removed = diff_min2 if removed_i == diff_min_i else diff_min

            min_dist_removed = min(
                min_dist_removed,
                max(
                    max_sum_removed - min_sum_removed,
                    max_diff_removed - min_diff_removed,
                ),
            )

        return min_dist_removed

unreasonably effective