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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimize Manhattan Distances

Number: 3344

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given an array of points on a 2D plane, each point represented as [x, y], the Manhattan distance between two points is defined as |x1 - x2| + |y1 - y2|. The task is to remove exactly one point such that the maximum Manhattan distance among all the remaining points is minimized. That is, for every possible removal, compute the maximum Manhattan distance between any pair of remaining points and return the minimum among those values.

Key Insights

  • The Manhattan distance between points (x1, y1) and (x2, y2) can be expressed as max(|(x1+y1) - (x2+y2)|, |(x1-y1) - (x2-y2)|). This transformation helps reduce the problem to tracking extreme values.
  • The maximum Manhattan distance among a set of points is determined by the range (difference between maximum and minimum) of either (x+y) or (x-y).
  • Removing a point that currently defines an extreme is what may cause a reduction in the overall distance; hence, you only need to consider points that are at one or more of the extremes.
  • Precompute sorted orders for both u = x+y and v = x-y coordinates so that if an extreme point is removed, the next extreme can be quickly determined.
  • Use prefix and suffix ideas (or simply tracking the smallest and second smallest, largest and second largest) for both sets of transformed values.

Space and Time Complexity

Time Complexity: O(n log n) – due to sorting the transformed arrays. Space Complexity: O(n) – additional arrays and data structures for storing transformed values and indices.

Solution

The solution proceeds as follows:

  1. Transform every point into two values: u = x+y and v = x-y.
  2. Identify the overall extreme values: u_min, u_max, v_min, and v_max.
  3. Only candidate removals that can affect these extreme values need to be considered. These candidates are those points whose u or v value equals one of the overall extremes.
  4. Pre-sort the points (with indices stored) based on the u values and similarly for the v values.
  5. For each candidate point, simulate its removal by determining the new u_min and u_max (if the candidate was an extreme in u) and the new v_min and v_max (if it was an extreme in v).
  6. The new maximum Manhattan distance among the remaining points is the maximum of (new_u_max - new_u_min) and (new_v_max - new_v_min).
  7. Return the minimum such maximum distance among all candidate removals.

This approach ensures that while looping only through a handful of candidate points, we can compute the resulting maximum Manhattan distance quickly without rescanning the entire list for every removal.

Code Solutions

# Python Solution with line-by-line comments

def minimize_max_distance(points):
    n = len(points)
    # Precompute transformed coordinates for each point: u = x+y, v = x-y.
    uv = [(points[i][0] + points[i][1], points[i][0] - points[i][1], i) for i in range(n)]
    
    # Create two separate lists for u and v along with original indices
    u_list = [(u, idx) for (u, v, idx) in uv]
    v_list = [(v, idx) for (u, v, idx) in uv]
    
    # Sort both lists on their values
    u_list.sort(key=lambda x: x[0])
    v_list.sort(key=lambda x: x[0])
    
    # Determine overall extreme values with corresponding indices
    u_min_val, u_min_idx = u_list[0]
    u_max_val, u_max_idx = u_list[-1]
    v_min_val, v_min_idx = v_list[0]
    v_max_val, v_max_idx = v_list[-1]
    
    # Gather candidate indices: only points that equal an extreme value.
    candidate_set = {u_min_idx, u_max_idx, v_min_idx, v_max_idx}
    
    # Helper function to get new extreme values if candidate 'remove_idx' is removed.
    def get_new_extremes(sorted_list, remove_idx):
        # If the candidate is at the beginning, then new min is the next element;
        # if at the end, new max is the previous element; otherwise, extremes remain.
        if sorted_list[0][1] == remove_idx:
            new_min = sorted_list[1][0]
        else:
            new_min = sorted_list[0][0]
        if sorted_list[-1][1] == remove_idx:
            new_max = sorted_list[-2][0]
        else:
            new_max = sorted_list[-1][0]
        return new_min, new_max

    result = float('inf')
    
    # Evaluate removal of each candidate.
    for remove_idx in candidate_set:
        new_u_min, new_u_max = get_new_extremes(u_list, remove_idx)
        new_v_min, new_v_max = get_new_extremes(v_list, remove_idx)
        # The maximum Manhattan distance among remaining points is defined by the maximum range
        curr_max_dist = max(new_u_max - new_u_min, new_v_max - new_v_min)
        result = min(result, curr_max_dist)
    
    return result

# Example usage:
points1 = [[3,10],[5,15],[10,2],[4,4]]
print(minimize_max_distance(points1))  # Output: 12

points2 = [[1,1],[1,1],[1,1]]
print(minimize_max_distance(points2))  # Output: 0
← Back to All Questions