#3102

Hard

LeetCode Problem Workspace

Minimize Manhattan Distances

Compute the minimum maximum Manhattan distance by removing one point using array math and geometry insights efficiently.

array math geometry sorting ordered set

Problem Statement

You are given a list of points on a 2D plane represented as an array points where each element points[i] = [xi, yi] is the integer coordinates of a point. The distance between two points is calculated using Manhattan distance, defined as |xi - xj| + |yi - yj|.

Your task is to remove exactly one point from the array such that the maximum Manhattan distance between any remaining pair of points is minimized. Return this minimal maximum distance. Constraints ensure there are at least three points, and coordinates are positive integers up to 10^8.

Examples

Example 1

Input: points = [[3,10],[5,15],[10,2],[4,4]]

Output: 12

The maximum distance after removing each point is the following: 12 is the minimum possible maximum distance between any two points after removing exactly one point.

Example 2

Input: points = [[1,1],[1,1],[1,1]]

Output: 0

Removing any of the points results in the maximum distance between any two points of 0.

Constraints

3 <= points.length <= 105
points[i].length == 2
1 <= points[i][0], points[i][1] <= 108

Solution Approach

Transform coordinates and identify extremes

Compute transformed values for each point using xi + yi and xi - yi. Track the maximum and minimum of these transformed values to identify candidates that influence the current maximum distance.

Evaluate removal scenarios

Check the effect of removing each candidate point that contributes to extreme transformed values. Calculate the resulting maximum distance after each removal and track the minimal value.

Return the minimal maximum distance

After evaluating all key removal candidates, return the smallest maximum Manhattan distance found. This avoids brute-force checking of all points while ensuring the solution is optimal.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on sorting or scanning the transformed arrays, typically O(n log n) or O(n) with careful selection. Space complexity is O(n) for storing transformed values and tracking extremes.

What Interviewers Usually Probe

Focus on using array math and Manhattan distance properties instead of brute-force pairwise comparisons.
Consider how removing extreme points affects the maximum distance efficiently.
Look for candidates by computing xi + yi and xi - yi to reduce unnecessary calculations.

Common Pitfalls or Variants

Common pitfalls

Attempting to check all possible removals without limiting to extreme candidates causes TLE.
Ignoring both xi + yi and xi - yi transformations can miss the true maximum distance.
Assuming Manhattan distance can be minimized by removing a random point rather than a critical extreme.

Follow-up variants

Minimizing Manhattan distance when removing multiple points instead of one.
Maximizing the minimum distance between points after removing a point.
Applying the same approach to 3D coordinates with Manhattan distance.

FAQ

What is the main idea behind minimizing Manhattan distance in this problem?

The main idea is to transform coordinates into xi + yi and xi - yi and remove the point contributing to extreme values to reduce the maximum distance.

Can we remove any point to minimize the maximum distance?

No, only points that are extremes in transformed coordinates affect the maximum distance significantly.

Does the solution require sorting?

Sorting transformed values helps identify extreme points efficiently, though scanning with tracking maxima and minima can achieve linear time.

Why use xi + yi and xi - yi transformations?

These transformations convert Manhattan distance evaluation into max-min comparisons along key axes, simplifying the distance calculation.

What array plus math pattern does this problem illustrate?

It illustrates using array transformation and extreme value tracking to reduce a global property, like maximum distance, by removing a single element.

terminal

Solution

Solution 1: Ordered Set

For two points $(x_1, y_1)$ and $(x_2, y_2)$, their Manhattan distance is $|x_1 - x_2| + |y_1 - y_2|$. We can transform it into $\max(x_1 - x_2, x_2 - x_1) + \max(y_1 - y_2, y_2 - y_1)$, which is:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        sl1 = SortedList()
        sl2 = SortedList()
        for x, y in points:
            sl1.add(x + y)
            sl2.add(x - y)
        ans = inf
        for x, y in points:
            sl1.remove(x + y)
            sl2.remove(x - y)
            ans = min(ans, max(sl1[-1] - sl1[0], sl2[-1] - sl2[0]))
            sl1.add(x + y)
            sl2.add(x - y)
        return ans

Continue Practicing

#3027 find the number of ways to place people ii #3025 find the number of ways to place people i #3380 maximum area rectangle with point constraints i