We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimize Manhattan Distances

Difficulty: Hard

Problem Description

You are given an array points representing integer coordinates of some points on a 2D plane, where points[i] = [xi, yi]. The distance between two points is defined as their Manhattan distance. Return the minimum possible value for maximum distance between any two points by removing exactly one point.

Key Insights

  • The Manhattan distance between two points (x1, y1) and (x2, y2) is calculated as |x1 - x2| + |y1 - y2|.
  • The maximum distance can be influenced significantly by extreme points (maximum and minimum x or y values).
  • By removing one point, we can potentially lower the maximum distance by affecting the extreme values.
  • A systematic approach to evaluate the maximum distances after removing each point is crucial.

Space and Time Complexity

Time Complexity: O(n log n) for sorting the points, and O(n) for evaluating each point removal. Space Complexity: O(1) if we consider only a constant amount of extra space for variables, O(n) if we include the space for sorting.

Solution

To solve the problem, we will:

  1. Sort the points based on their x and y coordinates to easily access extreme values.
  2. For each point, calculate the maximum Manhattan distance after removing that point.
  3. Track the minimum of these maximum distances across all removals.

We leverage sorting to efficiently find the max and min values of x and y coordinates in the remaining points after a point is removed, ensuring we only need to compute distances that involve these extremes.

Code Solutions

def minMaxDistance(points):
    points.sort()  # Sort by x-coordinate
    n = len(points)
    min_distance = float('inf')
    
    for i in range(n):
        # Calculate max distance when points[i] is removed
        x_vals = [points[j][0] for j in range(n) if j != i]
        y_vals = [points[j][1] for j in range(n) if j != i]
        
        max_x = max(x_vals)
        min_x = min(x_vals)
        max_y = max(y_vals)
        min_y = min(y_vals)
        
        max_distance = (max_x - min_x) + (max_y - min_y)
        min_distance = min(min_distance, max_distance)
    
    return min_distance
← Back to All Questions