Skip to main content
Talentd

Minimize Manhattan Distances - Solution & Explanation

HardArrayMathGeometrySorting22 min read
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Approach 1: Maximize and Minimize Projections

To solve the problem optimally, we need to consider how removing each point affects the maximum possible Manhattan distance. Instead of calculating all distances, we can utilize the mathematical properties of the Manhattan Distance. Every Manhattan Distance can be transformed into the form of linear combinations of the coordinates:

distance(p1, p2) = |x1 - x2| + |y1 - y2| can be considered as a maximum of combinations of (x + y), (x - y), (-x + y), (-x - y) after evaluating all possible sign combinations.

This approach leverages projections of points based on x+y and x-y.

The algorithm utilizes a transformation of the points:

  • Calculate transformed coordinates for each point using combinations of x+y and x-y.
  • Track minimal and maximal transformed projections.
  • Calculate the initial maximum distance based on projections.
  • Attempt to minimize the maximum distance by removing each point and recomputing the effective maximum Manhattan distance across the remaining points.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n) due to linear scans for projections and computations.
Space Complexity: O(n) for transformed list storage.

Try this approach in the editor β†’

Approach 2: Approach 2: Pre-compute Maximum Distances

A second approach involves computing the maximum Manhattan distance upfront and checking for reductions possible by removing one point. You accumulate results in an array or vector for precomputed distances.

This approach involves iteration with precomputation:

  • Track and transform input points to an intermediate form, as described.
  • Initialize metadata for minimal and maximal transformed values.
  • Iterate through the array, determining possible reductions in the largest Manhattan boundary through projected difference computations.

Code

C#

C#

Complexity

Time Complexity: O(n) similar to previous approach for a full iteration.
Space Complexity: O(n) for list usage.

Try this approach in the editor β†’

Approach 3: Ordered Set

For two points (x_1, y_1) and (x_2, y_2), their Manhattan distance is |x_1 - x_2| + |y_1 - y_2|. We can transform it into max(x_1 - x_2, x_2 - x_1) + max(y_1 - y_2, y_2 - y_1), which is:

$ |x_1 - x_2| + |y_1 - y_2| = max \begin{cases} x_1 - x_2 + y_1 - y_2 \ x_2 - x_1 + y_2 - y_1 \ x_1 - x_2 + y_2 - y_1 \ x_2 - x_1 + y_1 - y_2 \end{cases}

This can be simplified to:

|x_1 - x_2| + |y_1 - y_2| = max \begin{cases} (x_1 + y_1) - (x_2 + y_2) \ (x_2 + y_2) - (x_1 + y_1) \ (x_1 - y_1) - (x_2 - y_2) \ (x_2 - y_2) - (x_1 - y_1) \end{cases}

Here, the first two cases can be represented as max(max(x_1 + y_1, x_2 + y_2) - min(x_1 + y_1, x_2 + y_2)), and the last two cases can be represented as max(max(x_1 - y_1, x_2 - y_2) - min(x_1 - y_1, x_2 - y_2)).

Therefore, we can store all points according to the values of x + y and x - y in two ordered sets, respectively. Then, for each point, we remove it, update the values in the ordered sets, calculate the difference between the maximum and minimum values, and take the minimum value.

The time complexity is O(n log n), and the space complexity is O(n). Here, n$ is the number of points.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Approach 1: Maximize and Minimize Projections

Time Complexity: O(n) due to linear scans for projections and computations.
Space Complexity: O(n) for transformed list storage.

Approach 2: Pre-compute Maximum Distances

Time Complexity: O(n) similar to previous approach for a full iteration.
Space Complexity: O(n) for list usage.

Ordered Setβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Maximize and Minimize ProjectionsO(n)O(n)Best general solution. Uses (x+y) and (x-y) projections to track extremes efficiently.
Pre-compute Maximum Distances with Ordered StructureO(n log n)O(n)Useful when working with sorted containers or ordered sets where insertion/removal is needed.

Video Solution

3102. Minimize Manhattan Distances | Max Manhattan Distance between Any Points | Math β€’ Aryan Mittal β€’ 8,532 views views

Watch 6 more video solutions β†’

Frequently Asked Questions

Is Minimize Manhattan Distances easy or hard?
Minimize Manhattan Distances is classified as a Hard problem because it requires recognizing the geometric projection trick. A brute force approach is straightforward but too slow, while the optimal solution depends on transforming coordinates and tracking extreme values efficiently.
Minimize Manhattan Distances Python/Java solution
Python and C++ implementations typically compute x+y and x-y arrays and track the largest and smallest values with indices. During iteration, the algorithm checks how removing a point affects the extreme projections. The same logic can be implemented in Java, C++, Python, or C# with linear time complexity.
How to solve Minimize Manhattan Distances in O(n)?
Transform each point (x, y) into two projections: p = x + y and q = x - y. Track the largest and smallest values for both projections along with their second extremes. For each candidate removal, recompute the maximum difference using the remaining extremes. This avoids pairwise comparisons and keeps the algorithm linear.
What is the best approach for Minimize Manhattan Distances?
The optimal approach uses projection transformations with (x+y) and (x-y). By tracking the maximum and minimum values of these projections, you can identify the farthest Manhattan distances without comparing all pairs. Maintaining the top two extremes allows simulating removal of each point in O(n) total time.
Is Minimize Manhattan Distances asked at Google/Amazon/Meta?
Manhattan distance transformation problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving coordinate projections, geometry optimization, and extreme value tracking are common in senior-level algorithm rounds.
What data structure is used in Minimize Manhattan Distances?
Most efficient solutions use arrays to store projection values and track extreme elements. Some implementations use ordered sets or balanced trees to maintain sorted projections dynamically while removing and reinserting points.
What is the time complexity of Minimize Manhattan Distances?
The optimal projection-based solution runs in O(n) time and O(n) space. It scans all points once to compute projections and track extreme values. Alternative solutions using ordered sets or sorted containers typically run in O(n log n).

Ready to solve this problem?

Practice Minimize Manhattan Distances with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays