未分类

Maximum Manhattan Distance of Two Points in Points Set

未分类 2 min read

Manhattan Distance

Definition: The Manhattan distance between two points $(x_1, y_1)$ and $(x_2, y_2)$ in a 2D plane is defined as $dis = |x_1 - x_2| + |y_1 - y_2|$, where $| \cdot |$ denotes the absolute value.

Problem Definition

Given a set of points ${p_1, p_2, \ldots, p_n}$, where each point $p_i$ is represented by its coordinates $(x_i, y_i)$ in a 2D plane, the task is to find the maximum Manhattan distance between any two points $p_a$ and $p_b$ in the set. The desired time complexity for the solution is $O(n)$.

Solution

To avoid the absolute value operation in the definition of Manhattan distance, we can consider different cases based on the relative positions of the points:

  • Case 1: $dis_1 = x_1 - x_2 + y_1 - y_2$, when $x_1 > x_2$ and $y_1 > y_2$
  • Case 2: $dis_2 = x_2 - x_1 + y_1 - y_2$, when $x_1 < x_2$ and $y_1 > y_2$
  • Case 3: $dis_3 = x_1 - x_2 + y_2 - y_1$, when $x_1 > x_2$ and $y_1 < y_2$
  • Case 4: $dis_4 = x_2 - x_1 + y_2 - y_1$, when $x_1 < x_2$ and $y_1 < y_2$

By simplifying these expressions, we can rewrite them as:

  • Simplified Case 1: $dis_1 = (x_1 + y_1) - (x_2 + y_2)$
  • Simplified Case 2: $dis_2 = -(x_1 - y_1) - (x_2 - y_2)$
  • Simplified Case 3: $dis_3 = (x_1 - y_1) - (x_2 - y_2)$
  • Simplified Case 4: $dis_4 = -(x_1 + y_1) + (x_2 + y_2)$

From these simplified cases, we can deduce that the maximum Manhattan distance can be obtained by considering the following scenarios:

  • The maximum value of $(x+y)$ minus the minimum value of $(x+y)$
  • The minimum value of $(x-y)$ minus the minimum value of $(x-y)$
  • The maximum value of $(x-y)$ minus the minimum value of $(x-y)$
  • The minimum value of $(x+y)$ minus the maximum value of $(x+y)$

By iterating through the set of points and calculating these values, we can find the maximum Manhattan distance in $O(n)$ time complexity.

Here is Python code.

class Solution:
    def maxPoints(self, points):
        max_plus = max_minus = max_diff_plus = max_diff_minus = float('-inf')
        min_plus = min_minus = min_diff_plus = min_diff_minus = float('inf')
        max_plus_point = max_minus_point = max_diff_plus_point = max_diff_minus_point = None
        min_plus_point = min_minus_point = min_diff_plus_point = min_diff_minus_point = None

        for point in points:
            x, y = point
            if x + y > max_plus:
                max_plus = x + y
                max_plus_point = point
            if x + y < min_plus:
                min_plus = x + y
                min_plus_point = point
            if x - y > max_minus:
                max_minus = x - y
                max_minus_point = point
            if x - y < min_minus:
                min_minus = x - y
                min_minus_point = point
            if -x + y > max_diff_plus:
                max_diff_plus = -x + y
                max_diff_plus_point = point
            if -x + y < min_diff_plus:
                min_diff_plus = -x + y
                min_diff_plus_point = point
            if -x - y > max_diff_minus:
                max_diff_minus = -x - y
                max_diff_minus_point = point
            if -x - y < min_diff_minus:
                min_diff_minus = -x - y
                min_diff_minus_point = point

        distances = {
            (max_plus - min_plus): (max_plus_point, min_plus_point),
            (max_minus - min_minus): (max_minus_point, min_minus_point),
            (max_diff_plus - min_diff_plus): (max_diff_plus_point, min_diff_plus_point),
            (max_diff_minus - min_diff_minus): (max_diff_minus_point, min_diff_minus_point)
        }

        max_distance = max(distances.keys())
        return distances[max_distance], max_distance

Read more