Minimize Manhattan Distances
HardPrompt
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 <= 105points[i].length == 21 <= points[i][0], points[i][1] <= 108
Approaches
3 approaches with complexity analysis and trade-offs.
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.
Algorithm
- Initialize
min_max_distanceto a very large value. - Loop through each point
p_ifromi = 0ton-1to be removed. - Create a temporary list of points,
temp_points, by copying all points from the input exceptp_i. - Initialize
current_max_distance = 0. - Loop through all unique pairs of points
(p_j, p_k)intemp_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_pointshas fewer than two points, the distance is 0. Otherwise, it'scurrent_max_distance. - Update
min_max_distance = min(min_max_distance, current_max_distance). - Return
min_max_distance.
Walkthrough
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.
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<int[]> 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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- The Manhattan distance
|x1 - x2| + |y1 - y2|is equivalent to the Chebyshev distancemax(|u1 - u2|, |v1 - v2|)on transformed coordinatesu = x + yandv = x - y. - The maximum Chebyshev distance in a set of points is
max(max(u) - min(u), max(v) - min(v)). - Initialize
min_max_distanceto a large value. - Loop through each point
p_ito be removed. - For the remaining
n-1points, find the minimum and maximum of theiruandvcoordinates. - Calculate the
current_max_distancefor this subset asmax(max_u - min_u, max_v - min_v). - Update
min_max_distance = min(min_max_distance, current_max_distance). - Return
min_max_distance.
Walkthrough
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).
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; }}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.
Trade-offs
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.
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.
Algorithm
- For each point
p_i = (x_i, y_i), calculate the transformed coordinatesu_i = x_i + y_iandv_i = x_i - y_i. - Create two lists of pairs,
u_listandv_list, where each element is(value, original_index). - Sort both
u_listandv_listbased on their values. - This gives us easy access to the points with min, second-min, max, and second-max
uandvvalues. - Initialize
min_max_distanceto a large value. - Loop through each point
p_ito be removed. - To find the new
u_range, check ifp_icorresponds to the global min or maxu. 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.
Walkthrough
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.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
class Solution {public int minimumDistance(int[][] points) { TreeMap<Integer, Integer> tm1 = new TreeMap<>(); TreeMap<Integer, Integer> 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; }}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 ansclass Solution {public: int minimumDistance(vector<vector<int>> &points) { multiset<int> st1; multiset<int> 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; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.