Watch 10 video solutions for Minimize Manhattan Distances, a hard level problem involving Array, Math, Geometry. This walkthrough by Aryan Mittal has 8,124 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
|5 - 10| + |15 - 2| = 18.|3 - 10| + |10 - 2| = 15.|5 - 4| + |15 - 4| = 12.|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] <= 108Problem Overview: You are given points on a 2D grid. Remove exactly one point so that the maximum Manhattan distance between any remaining pair of points becomes as small as possible. The challenge is computing this efficiently without checking every pair after every removal.
Approach 1: Maximize and Minimize Projections (O(n) time, O(n) space)
The key observation comes from geometry: Manhattan distance |x1 - x2| + |y1 - y2| can be transformed using projections. If you define p = x + y and q = x - y, then the Manhattan distance between two points becomes the maximum difference across these projections. Instead of comparing every pair, compute the maximum and minimum values of p and q. The farthest pair must involve these extremes. To simulate removing a point, track the top two maxima and minima for both projections. When you remove a candidate point, recompute the distance using the second-best extremes if necessary. This avoids recomputing everything and reduces the problem to a single pass over the points. The result is an efficient linear-time solution that only stores projection values in arrays.
Approach 2: Pre-compute Maximum Distances (O(n log n) time, O(n) space)
Another approach keeps the projection values inside an ordered structure. Compute x+y and x-y for each point and store them in ordered containers or sorted arrays. These allow quick access to current minimum and maximum values. For every point, temporarily remove its projections from the structure, calculate the maximum Manhattan distance using the remaining extremes, and insert it back. The ordered container guarantees O(log n) updates and queries. This method is conceptually simpler if you already use sorting or ordered sets, though it is slightly slower than the linear projection trick.
Both strategies rely on the same geometric transformation but differ in how they maintain extremes. Instead of pairwise comparisons, the solution reduces the entire search space to just four critical values: max/min of x+y and max/min of x-y. This drastically cuts down the work required.
Recommended for interviews: The projection-based solution is the expected answer. It demonstrates understanding of Manhattan distance transformations and reduces the problem to an O(n) scan over the array of points. Showing the brute-force reasoning first helps justify the optimization, but interviewers typically look for the projection insight.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Maximize and Minimize Projections | O(n) | O(n) | Best general solution. Uses (x+y) and (x-y) projections to track extremes efficiently. |
| Pre-compute Maximum Distances with Ordered Structure | O(n log n) | O(n) | Useful when working with sorted containers or ordered sets where insertion/removal is needed. |