Leetcode 3102: Minimize Manhattan Distances

You are given a 0-indexed 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.

Example 1:

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.
It can be seen that 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
Explanation: It can be seen that 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

Problem Analysis:

If we iterate to compute all distances between points, the time complexity will be O(n²).

Assume the ith point P_i’s coordinate is (x_i, y_i). So Manhattan distance between P_i and P_j is |x_i-x_j| + |y_i-y_j|. In details there are 4 cases:

1. if x_i ≥ x_j and y_i ≥ y_j then Manhattan distance is (x_i + y_i)-(x_j+y_j)
2. if x_i < x_j and y_i < y_j then -(x_i+y_i)+(x_j+y_j)
3. if x_i ≥ x_j and y_i < y_j then (x_i-y_i)-(x_j-y_j)
4. if x_i < x_j and y_i ≥ y_j then -(x_i-y_i)+(x_j-y_j)

So we set sum(i) = x_i + y_i, diff(i) = x_i-y_i. Then

max Manhattan(P_i, P_j) = max(max(|sum(i)-sum(j)|, |diff(i)-diff(j)|)

Solution

class Solution {
public:
    int minimumDistance(vector<vector<int>>& points) {
        int x;
        int y;
        help(points, -1, x, y);
        int k, m;
        return min(help(points, x, k, m), help(points, y, k, m));
    }
    
    int help(vector<vector<int>>& points, int except, int& x, int& y) {
        array<int, 2> sum{INT_MAX, INT_MIN};
        array<int, 2> sum_i{0, 0};
        array<int, 2> diff{INT_MAX, INT_MIN};
        array<int, 2> diff_i{0, 0};

        for (int i = 0; i < points.size(); ++i) {
            if (i == except) continue;
            if (sum[0] > points[i][0] + points[i][1]) {
                sum[0] = points[i][0] + points[i][1];
                sum_i[0] = i;
            }
            if (sum[1] < points[i][0] + points[i][1]) {
                sum[1] = points[i][0] + points[i][1];
                sum_i[1] = i;
            }
            if (diff[0] > points[i][0] - points[i][1]) {
                diff[0] = points[i][0] - points[i][1];
                diff_i[0] = i;
            }
            if (diff[1] < points[i][0] - points[i][1]) {
                diff[1] = points[i][0] - points[i][1];
                diff_i[1] = i;
            }
        }
        if (sum[1] - sum[0] > diff[1] - diff[0]) {
            x = sum_i[0];
            y = sum_i[1];
            return sum[1] - sum[0];
        }

        x = diff_i[0];
        y = diff_i[1];
        return diff[1] - diff[0];
    }
};

Time complexity is O(n)

Space complexity is O(1)