LeetCode 3102 - Minimize Manhattan Distances

The problem asks us to minimize the maximum Manhattan distance between any two points on a 2D plane after removing exactly one point from the input list. The input points is an array of integer coordinates [[x1, y1], [x2, y2], ..., [xn, yn]].

leetcodehardarraymathgeometrysortingordered-set

LeetCode Problem 3102

Difficulty: 🔴 Hard
Topics: Array, Math, Geometry, Sorting, Ordered Set

Solution

Problem Understanding

The problem asks us to minimize the maximum Manhattan distance between any two points on a 2D plane after removing exactly one point from the input list. The input points is an array of integer coordinates [[x1, y1], [x2, y2], ..., [xn, yn]]. The Manhattan distance between two points (x1, y1) and (x2, y2) is defined as |x1 - x2| + |y1 - y2|.

We are tasked with identifying the point whose removal results in the smallest possible maximum Manhattan distance between any remaining pair of points. The output is this minimized maximum distance.

The constraints indicate that 3 <= points.length <= 10^5 and each coordinate can be as large as 10^8. This means a naive O(n^2) approach that checks every pair after removing each point will be far too slow. Inputs can be large, and we need an efficient approach that scales linearly or near-linearly with the number of points.

Important edge cases include:

  1. All points are identical, which would trivially return 0.
  2. Points forming a line or rectangle, where extremes dominate the maximum distance.
  3. The maximum distance involves a corner point; removing a non-corner point does not reduce it.

Approaches

Brute Force

A brute-force approach iterates through each point, temporarily removes it, and calculates the maximum Manhattan distance among the remaining points. This requires computing the distance for all O(n^2) pairs per removal, resulting in O(n^3) complexity. While correct, this is infeasible for n up to 10^5.

Key Insight

The Manhattan distance |x1 - x2| + |y1 - y2| can be transformed using the idea that max(|x1-x2|+|y1-y2|) = max(|x+y| difference, |x-y| difference). Specifically, define:

  • u = x + y
  • v = x - y

Then the Manhattan distance between two points becomes max(|u1 - u2|, |v1 - v2|). Therefore, the maximum Manhattan distance is determined by the points with the maximum and minimum u and v values. Only these extreme points matter; removing any other point cannot reduce the maximum distance.

This reduces the problem to identifying the extreme points, considering the removal of one of them, and recalculating the maximum distance among the remaining extremes. This can be done in O(n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Check maximum distance for all pairs after removing each point. Too slow for large n.
Optimal O(n) O(n) Track extreme points for x+y and x-y, consider removal of each extreme, compute new max distance. Efficient and scalable.

Algorithm Walkthrough

  1. Transform all points into two forms u = x + y and v = x - y.

  2. Identify the points with maximum and minimum values for u and v. These points are the extremes that contribute to the maximum Manhattan distance.

  3. Consider each extreme point as a candidate for removal. For each candidate:

  4. Remove the point.

  5. Compute the maximum u difference and maximum v difference among the remaining points.

  6. Take the maximum of these two differences; this is the maximum Manhattan distance after removal.

  7. Track the minimum value obtained from step 3 for all candidate removals.

  8. Return the minimum as the result.

Why it works: The maximum Manhattan distance is only influenced by the extreme points in terms of x + y and x - y. Removing any point that is not an extreme does not reduce the maximum distance. Therefore, it suffices to only consider removals among these extreme points, guaranteeing correctness and efficiency.

Python Solution

from typing import List

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        n = len(points)
        if n <= 3:
            return 0
        
        u = [x + y for x, y in points]
        v = [x - y for x, y in points]
        
        # Identify extreme values
        max_u, min_u = max(u), min(u)
        max_v, min_v = max(v), min(v)
        
        # Track indices of extreme points
        extreme_indices = set()
        for i in range(n):
            if u[i] == max_u or u[i] == min_u or v[i] == max_v or v[i] == min_v:
                extreme_indices.add(i)
        
        result = float('inf')
        
        # Try removing each extreme point
        for idx in extreme_indices:
            u_remaining = [u[i] for i in range(n) if i != idx]
            v_remaining = [v[i] for i in range(n) if i != idx]
            max_distance = max(max(u_remaining) - min(u_remaining),
                               max(v_remaining) - min(v_remaining))
            result = min(result, max_distance)
        
        return result

Explanation: First, we compute transformed coordinates u and v. Then, we identify the indices of points that are extreme in any transformed coordinate. Removing non-extreme points is pointless, so we only iterate over these. For each candidate removal, we compute the remaining maximum differences and track the smallest among them.

Go Solution

package main

func minimumDistance(points [][]int) int {
    n := len(points)
    if n <= 3 {
        return 0
    }

    u := make([]int, n)
    v := make([]int, n)
    for i := 0; i < n; i++ {
        u[i] = points[i][0] + points[i][1]
        v[i] = points[i][0] - points[i][1]
    }

    maxU, minU := u[0], u[0]
    maxV, minV := v[0], v[0]
    for i := 1; i < n; i++ {
        if u[i] > maxU {
            maxU = u[i]
        }
        if u[i] < minU {
            minU = u[i]
        }
        if v[i] > maxV {
            maxV = v[i]
        }
        if v[i] < minV {
            minV = v[i]
        }
    }

    extremeIndices := make(map[int]bool)
    for i := 0; i < n; i++ {
        if u[i] == maxU || u[i] == minU || v[i] == maxV || v[i] == minV {
            extremeIndices[i] = true
        }
    }

    result := int(1e18)
    for idx := range extremeIndices {
        maxUR, minUR := -1<<60, 1<<60
        maxVR, minVR := -1<<60, 1<<60
        for i := 0; i < n; i++ {
            if i == idx {
                continue
            }
            if u[i] > maxUR {
                maxUR = u[i]
            }
            if u[i] < minUR {
                minUR = u[i]
            }
            if v[i] > maxVR {
                maxVR = v[i]
            }
            if v[i] < minVR {
                minVR = v[i]
            }
        }
        maxDistance := max(maxUR - minUR, maxVR - minVR)
        if maxDistance < result {
            result = maxDistance
        }
    }

    return result
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Go Notes: The Go solution mirrors the Python logic, with explicit tracking of extreme values using slices. Because Go has no built-in sets, we use a map to track extreme indices. Integer overflow is avoided by using large sentinel values for comparisons.

Worked Examples

Example 1: [[3,10],[5,15],[10,2],[4,4]]

Point Removed Remaining Points Max u = x+y Max v = x-y Max Manhattan Distance
0 [5,15],[10,2],[4,4] max(20-6)=14 max(13-(-2))=15 15
1 [3,10],[10,2],[4,4] max(14-6)=8 max(8-(-2))=10 10
2 [3,10],[5,15],[4,4] max(20-7)=13 max(11-(-1))=12 12
3 [3,10],[5,15],[10,2] max(20-8)=12 max(13-(-8))=21 21

Minimum distance after removal = 12.

Example 2: [[1,1],[1,1],[1,1]]

All points identical, removing any results in 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Compute transformed coordinates and