# Minimize Manhattan Distances **Difficulty:** HARD [External](https://leetcode.com/problems/minimize-manhattan-distances) Canonical: https://scaleengineer.com/dsa/problems/minimize-manhattan-distances **Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Geometry](https://scaleengineer.com/dsa/patterns/geometry) **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting) **Data structures:** Array, Ordered Set **Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank) --- ## 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 _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`. 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:** 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` # Approaches ## Brute Force Simulation This approach directly simulates the process described in the problem. We iterate through each point, considering it for removal. For each removal, we form a new set of points and then find the maximum Manhattan distance within this new set by checking every possible pair of points. **Time:** O(N^3), where N is the number of points. The outer loop runs N times. For each removal, we iterate through O(N^2) pairs of the remaining points. · **Space:** O(N), to store the temporary list of points for each removal. **Pros:** Simple to understand and implement.; Directly follows the problem statement. **Cons:** Extremely inefficient due to the triple nested loop structure.; Will result in a 'Time Limit Exceeded' error for the given constraints. ### Explanation The brute-force method involves a straightforward simulation. We use an outer loop to select a point to remove. Inside this loop, we construct a new list of the remaining `n-1` points. Then, with two more nested loops, we iterate through every possible pair of points in this new list, calculate their Manhattan distance, and keep track of the maximum distance found. This maximum distance is one candidate for our final answer. We repeat this process for every point, and the minimum of these maximum distances is the result. ```java class Solution { public int minimumMaxDistance(int[][] points) { int n = points.length; if (n <= 2) { return 0; } int minMaxDist = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { // Point to remove java.util.List tempList = new java.util.ArrayList<>(); for (int j = 0; j < n; j++) { if (i != j) { tempList.add(points[j]); } } int currentMaxDist = 0; for (int j = 0; j < tempList.size(); j++) { for (int k = j + 1; k < tempList.size(); k++) { int[] p1 = tempList.get(j); int[] p2 = tempList.get(k); int dist = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]); currentMaxDist = Math.max(currentMaxDist, dist); } } minMaxDist = Math.min(minMaxDist, currentMaxDist); } return minMaxDist; } } ``` ### Algorithm - Initialize `min_max_distance` to a very large value. - Loop through each point `p_i` from `i = 0` to `n-1` to be removed. - Create a temporary list of points, `temp_points`, by copying all points from the input except `p_i`. - Initialize `current_max_distance = 0`. - Loop through all unique pairs of points `(p_j, p_k)` in `temp_points`. - Calculate the Manhattan distance `d = |p_j.x - p_k.x| + |p_j.y - p_k.y|`. - Update `current_max_distance = max(current_max_distance, d)`. - After checking all pairs, if `temp_points` has fewer than two points, the distance is 0. Otherwise, it's `current_max_distance`. - Update `min_max_distance = min(min_max_distance, current_max_distance)`. - Return `min_max_distance`. ## Optimized Calculation using Coordinate Transformation This approach improves upon the brute force method by optimizing how the maximum distance is calculated for each subset of points. Instead of checking all pairs, we use a mathematical property of Manhattan distance. By transforming the coordinates, we can find the maximum distance in linear time for a given set of points, reducing the overall complexity. **Time:** O(N^2). The outer loop runs N times, and the inner loop to find min/max of transformed coordinates also runs N times. · **Space:** O(1), as we only use a few variables to track min/max values. **Pros:** Significantly more efficient than the O(N^3) approach.; Avoids creating temporary lists, reducing space overhead. **Cons:** Still too slow for the given constraints as it involves nested loops. ### Explanation We can optimize the inner part of the brute-force approach. The key insight is the relationship between Manhattan distance and Chebyshev distance. The Manhattan distance between `(x1, y1)` and `(x2, y2)` is `|x1 - x2| + |y1 - y2|`. This is equal to `max(|(x1+y1) - (x2+y2)|, |(x1-y1) - (x2-y2)|)`. If we transform each point `(x, y)` to `(u, v) = (x+y, x-y)`, the problem becomes finding the maximum Chebyshev distance. The maximum Chebyshev distance in a set of transformed points is simply `max(max(u) - min(u), max(v) - min(v))`. So, for each point we remove, we can find the max distance among the remaining points in `O(N)` time by finding the min/max of their `u` and `v` values, instead of `O(N^2)`. ```java class Solution { public int minimumMaxDistance(int[][] points) { int n = points.length; int minMaxDist = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { // Point to remove int minU = Integer.MAX_VALUE; int maxU = Integer.MIN_VALUE; int minV = Integer.MAX_VALUE; int maxV = Integer.MIN_VALUE; for (int j = 0; j < n; j++) { if (i == j) continue; int u = points[j][0] + points[j][1]; int v = points[j][0] - points[j][1]; minU = Math.min(minU, u); maxU = Math.max(maxU, u); minV = Math.min(minV, v); maxV = Math.max(maxV, v); } int currentMaxDist = 0; if (n > 1) { // If there are points left currentMaxDist = Math.max(maxU - minU, maxV - minV); } minMaxDist = Math.min(minMaxDist, currentMaxDist); } return minMaxDist; } } ``` ### Algorithm - The Manhattan distance `|x1 - x2| + |y1 - y2|` is equivalent to the Chebyshev distance `max(|u1 - u2|, |v1 - v2|)` on transformed coordinates `u = x + y` and `v = x - y`. - The maximum Chebyshev distance in a set of points is `max(max(u) - min(u), max(v) - min(v))`. - Initialize `min_max_distance` to a large value. - Loop through each point `p_i` to be removed. - For the remaining `n-1` points, find the minimum and maximum of their `u` and `v` coordinates. - Calculate the `current_max_distance` for this subset as `max(max_u - min_u, max_v - min_v)`. - Update `min_max_distance = min(min_max_distance, current_max_distance)`. - Return `min_max_distance`. ## Optimal Approach with Pre-sorting This is the most efficient approach, which builds upon the coordinate transformation idea. The bottleneck in the `O(N^2)` approach is re-calculating the min/max of `u` and `v` values from scratch for each removed point. We can optimize this by pre-processing. By sorting the `u` and `v` values (while keeping track of their original indices), we can find the top two and bottom two values for both `u` and `v` for the entire set. Then, for each point we consider removing, we can determine the new min/max values in `O(1)` time. **Time:** O(N log N), dominated by the sorting step. The final loop to calculate the minimum max distance runs in O(N). · **Space:** O(N), to store the lists of transformed coordinates with their original indices. **Pros:** Highly efficient and passes within the time limits for the given constraints.; The core logic after sorting is very fast (O(1) per removal). **Cons:** More complex to implement due to sorting and handling indices.; Requires extra space to store the transformed coordinates and their indices. ### Explanation The key to an optimal solution is to avoid re-computation. We first transform all points `(x, y)` to `(u, v) = (x+y, x-y)`. Then, we create two lists, one for `u` values and one for `v` values, storing both the value and the original index of the point. We sort both lists. After sorting, `u_list[0]` holds the point with the minimum `u` value, `u_list[1]` the second minimum, `u_list[n-1]` the maximum, and so on. Now, we iterate through each point `i` to be removed. To find the maximum distance in the remaining set, we need the new `max(u) - min(u)` and `max(v) - min(v)`. The new `max(u)` is `u_list[n-1].val` unless point `i` is the one with the maximum `u` value (i.e., `i == u_list[n-1].index`), in which case the new `max(u)` is `u_list[n-2].val`. A similar logic applies to finding the new `min(u)`, `max(v)`, and `min(v)`. This allows us to calculate the max distance for each removal in `O(1)` time after the initial `O(N log N)` sort. ```java import java.util.Arrays; import java.util.Comparator; class Solution { public int minimumMaxDistance(int[][] points) { int n = points.length; class Pair { int val; int index; Pair(int val, int index) { this.val = val; this.index = index; } } Pair[] uList = new Pair[n]; Pair[] vList = new Pair[n]; for (int i = 0; i < n; i++) { uList[i] = new Pair(points[i][0] + points[i][1], i); vList[i] = new Pair(points[i][0] - points[i][1], i); } Arrays.sort(uList, Comparator.comparingInt(p -> p.val)); Arrays.sort(vList, Comparator.comparingInt(p -> p.val)); int minMaxDist = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { // Point to remove at original index i // Calculate u_range int uMaxVal, uMinVal; if (uList[n - 1].index == i) { // if removed point is max u uMaxVal = uList[n - 2].val; } else { uMaxVal = uList[n - 1].val; } if (uList[0].index == i) { // if removed point is min u uMinVal = uList[1].val; } else { uMinVal = uList[0].val; } int uRange = uMaxVal - uMinVal; // Calculate v_range int vMaxVal, vMinVal; if (vList[n - 1].index == i) { // if removed point is max v vMaxVal = vList[n - 2].val; } else { vMaxVal = vList[n - 1].val; } if (vList[0].index == i) { // if removed point is min v vMinVal = vList[1].val; } else { vMinVal = vList[0].val; } int vRange = vMaxVal - vMinVal; int currentMaxDist = Math.max(uRange, vRange); minMaxDist = Math.min(minMaxDist, currentMaxDist); } return minMaxDist; } } ``` ### Algorithm - For each point `p_i = (x_i, y_i)`, calculate the transformed coordinates `u_i = x_i + y_i` and `v_i = x_i - y_i`. - Create two lists of pairs, `u_list` and `v_list`, where each element is `(value, original_index)`. - Sort both `u_list` and `v_list` based on their values. - This gives us easy access to the points with min, second-min, max, and second-max `u` and `v` values. - Initialize `min_max_distance` to a large value. - Loop through each point `p_i` to be removed. - To find the new `u_range`, check if `p_i` corresponds to the global min or max `u`. If it does, the new min/max will be the second-min/max value. Otherwise, the min/max remains the same. - Do the same for the `v_range`. - The max distance for this removal is `max(u_range, v_range)`. - Update the overall `min_max_distance`. - Return `min_max_distance`. # Solutions ### Java ```java class Solution { public int minimumDistance(int[][] points) { TreeMap tm1 = new TreeMap<>(); TreeMap tm2 = new TreeMap<>(); for (int[] p : points) { int x = p[0], y = p[1]; tm1.merge(x + y, 1, Integer : : sum); tm2.merge(x - y, 1, Integer : : sum); } int ans = Integer.MAX_VALUE; for (int[] p : points) { int x = p[0], y = p[1]; if (tm1.merge(x + y, -1, Integer : : sum) == 0) { tm1.remove(x + y); } if (tm2.merge(x - y, -1, Integer : : sum) == 0) { tm2.remove(x - y); } ans = Math.min(ans, Math.max(tm1.lastKey() - tm1.firstKey(), tm2.lastKey() - tm2.firstKey())); tm1.merge(x + y, 1, Integer : : sum); tm2.merge(x - y, 1, Integer : : sum); } return ans; } } ``` ### Python ```python from sortedcontainers import SortedList 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 ``` ### CPP ```cpp class Solution { public: int minimumDistance(vector> &points) { multiset st1; multiset st2; for (auto &p : points) { int x = p[0], y = p[1]; st1.insert(x + y); st2.insert(x - y); } int ans = INT_MAX; for (auto &p : points) { int x = p[0], y = p[1]; st1.erase(st1.find(x + y)); st2.erase(st2.find(x - y)); ans = min( ans, max(*st1.rbegin() - *st1.begin(), *st2.rbegin() - *st2.begin())); st1.insert(x + y); st2.insert(x - y); } return ans; } }; ```