Minimize Manhattan Distances

Problem

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 theminimum possible value for maximum distance between any two points by removing exactly one point.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16



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

Output: 12

Explanation:

The maximum distance after removing each point is the following:

  * After removing the 0th point the maximum distance is between points (5, 15) and (10, 2), which is `|5 - 10| + |15 - 2| = 18`.
  * After removing the 1st point the maximum distance is between points (3, 10) and (10, 2), which is `|3 - 10| + |10 - 2| = 15`.
  * After removing the 2nd point the maximum distance is between points (5, 15) and (4, 4), which is `|5 - 4| + |15 - 4| = 12`.
  * After removing the 3rd point the maximum distance is between points (5, 15) and (10, 2), which is `|5 - 10| + |15 - 2| = 18`.

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

Example 2

1
2
3
4
5
6
7
8
9



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

Output: 0

Explanation:

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

Constraints

3 <= points.length <= 10^5
points[i].length == 2
1 <= points[i][0], points[i][1] <= 10^8

Solution

Method 1 – Extreme Value Analysis (Geometry)

Intuition

The maximum Manhattan distance between any two points is determined by the extreme values of x + y and x - y. By removing one point, we can potentially reduce the spread of these values, thus minimizing the maximum distance.

Approach

For each point, compute x + y and x - y.
Find the four extreme values: max/min of x + y and max/min of x - y.
For each point, consider removing it and recompute the extreme values (excluding that point).
For each removal, calculate the new maximum Manhattan distance.
Return the minimum possible maximum distance after removing one point.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


class Solution {
public:
    int minimizeManhattan(vector<vector<int>>& points) {
        int n = points.size();
        vector<int> a, b;
        for (auto& p : points) {
            a.push_back(p[0] + p[1]);
            b.push_back(p[0] - p[1]);
        }
        auto get_extremes = [](const vector<int>& v, int skip) {
            int mx = INT_MIN, mn = INT_MAX;
            for (int i = 0; i < v.size(); ++i) {
                if (i == skip) continue;
                mx = max(mx, v[i]);
                mn = min(mn, v[i]);
            }
            return mx - mn;
        };
        int ans = INT_MAX;
        for (int i = 0; i < n; ++i) {
            int d1 = get_extremes(a, i);
            int d2 = get_extremes(b, i);
            ans = min(ans, max(d1, d2));
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


func minimizeManhattan(points [][]int) int {
    n := len(points)
    a, b := make([]int, n), make([]int, n)
    for i, p := range points {
        a[i] = p[0] + p[1]
        b[i] = p[0] - p[1]
    }
    getExtremes := func(v []int, skip int) int {
        mx, mn := -1<<31, 1<<31-1
        for i := 0; i < n; i++ {
            if i == skip { continue }
            if v[i] > mx { mx = v[i] }
            if v[i] < mn { mn = v[i] }
        }
        return mx - mn
    }
    ans := 1<<31-1
    for i := 0; i < n; i++ {
        d1 := getExtremes(a, i)
        d2 := getExtremes(b, i)
        if max(d1, d2) < ans { ans = max(d1, d2) }
    }
    return ans
}
func max(a, b int) int { if a > b { return a } else { return b } }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
    public int minimizeManhattan(int[][] points) {
        int n = points.length;
        int[] a = new int[n], b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = points[i][0] + points[i][1];
            b[i] = points[i][0] - points[i][1];
        }
        int ans = Integer.MAX_VALUE;
        for (int skip = 0; skip < n; skip++) {
            int mx1 = Integer.MIN_VALUE, mn1 = Integer.MAX_VALUE;
            int mx2 = Integer.MIN_VALUE, mn2 = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (i == skip) continue;
                mx1 = Math.max(mx1, a[i]); mn1 = Math.min(mn1, a[i]);
                mx2 = Math.max(mx2, b[i]); mn2 = Math.min(mn2, b[i]);
            }
            ans = Math.min(ans, Math.max(mx1 - mn1, mx2 - mn2));
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution {
    fun minimizeManhattan(points: Array<IntArray>): Int {
        val n = points.size
        val a = IntArray(n) { points[it][0] + points[it][1] }
        val b = IntArray(n) { points[it][0] - points[it][1] }
        var ans = Int.MAX_VALUE
        for (skip in 0 until n) {
            var mx1 = Int.MIN_VALUE; var mn1 = Int.MAX_VALUE
            var mx2 = Int.MIN_VALUE; var mn2 = Int.MAX_VALUE
            for (i in 0 until n) {
                if (i == skip) continue
                mx1 = maxOf(mx1, a[i]); mn1 = minOf(mn1, a[i])
                mx2 = maxOf(mx2, b[i]); mn2 = minOf(mn2, b[i])
            }
            ans = minOf(ans, maxOf(mx1 - mn1, mx2 - mn2))
        }
        return ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def minimize_manhattan(points: list[list[int]]) -> int:
    n = len(points)
    a = [x + y for x, y in points]
    b = [x - y for x, y in points]
    ans = float('inf')
    for skip in range(n):
        mx1 = max(a[i] for i in range(n) if i != skip)
        mn1 = min(a[i] for i in range(n) if i != skip)
        mx2 = max(b[i] for i in range(n) if i != skip)
        mn2 = min(b[i] for i in range(n) if i != skip)
        ans = min(ans, max(mx1 - mn1, mx2 - mn2))
    return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


impl Solution {
    pub fn minimize_manhattan(points: Vec<Vec<i32>>) -> i32 {
        let n = points.len();
        let a: Vec<i32> = points.iter().map(|p| p[0] + p[1]).collect();
        let b: Vec<i32> = points.iter().map(|p| p[0] - p[1]).collect();
        let mut ans = i32::MAX;
        for skip in 0..n {
            let mx1 = a.iter().enumerate().filter(|(i, _)| *i != skip).map(|(_, v)| *v).max().unwrap();
            let mn1 = a.iter().enumerate().filter(|(i, _)| *i != skip).map(|(_, v)| *v).min().unwrap();
            let mx2 = b.iter().enumerate().filter(|(i, _)| *i != skip).map(|(_, v)| *v).max().unwrap();
            let mn2 = b.iter().enumerate().filter(|(i, _)| *i != skip).map(|(_, v)| *v).min().unwrap();
            ans = ans.min(mx1 - mn1).max(mx2 - mn2);
        }
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution {
    minimizeManhattan(points: number[][]): number {
        const n = points.length;
        const a = points.map(([x, y]) => x + y);
        const b = points.map(([x, y]) => x - y);
        let ans = Infinity;
        for (let skip = 0; skip < n; ++skip) {
            const mx1 = Math.max(...a.filter((_, i) => i !== skip));
            const mn1 = Math.min(...a.filter((_, i) => i !== skip));
            const mx2 = Math.max(...b.filter((_, i) => i !== skip));
            const mn2 = Math.min(...b.filter((_, i) => i !== skip));
            ans = Math.min(ans, Math.max(mx1 - mn1, mx2 - mn2));
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n^2), for recomputing extremes for each removal.
🧺 Space complexity: O(n), for storing transformed coordinates.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Extreme Value Analysis (Geometry)#

Intuition#

Approach#

Code#

Complexity#