Solution: Minimize Manhattan Distances

Statement

You are given an array, points, where each element in points[i] $= [x_j, y_i]$ represents the integer coordinates of a point in a 2D plane. The distance between any two points is defined as the Manhattan distanceThe Manhattan distance between two cells (x1, y1) and (x2, y2) is |x_1 - x_2| + |y_1 - y_2|..

Your task is to determine and return the smallest possible value for the maximum distance between any two points after removing exactly one point from the array.

Constraints:

• $3 \leq$ points.length $\leq 10^3$

• points[i].length $== 2$

• $1 \leq$ points[i][0], points[i][1] $\leq 10^3$

Solution

This solution calculates the minimum possible maximum Manhattan distance between any two points by analyzing the properties of the Manhattan metric in a 2D coordinate plane. The essence of the solution lies in observing that the sums and differences of the coordinates determine the Manhattan distance. By focusing on the extreme values of these sums and differences, we can identify the optimal point to remove to minimize the maximum distance.

Intuition:

The Manhattan distance between two points $P_i=(x_i,y_i)$ and $P_j=(x_j​,y_j​)$ is:

$\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\text{Manhattan}(P_i,P_j)=∣x_i−x_j∣+∣y_i−y_j∣$

This can be rewritten as:

$Manhattan=max \{ x_1​−x_2​+y_1​−y_2​,x_1​−x_2​−y_1​+y_2​,−x_1​+x_2​+y_1​−y_2​,−x_1+x_2​−y_1​+y_2 \}$

Let’s use:

• $s=x+y$ (The sum of coordinates)

• $d = x - y$ (The difference of coordinates)

Then, the Manhattan distance becomes:

$\space\space\space\space\space\space\space\space\space\space\space\space\space\text{Manhattan}=max⁡(∣s_1−s_2∣,∣d_1−d_2∣)$

So, the above equation simplifies the problem by reducing it to analyzing the extreme values of $s$ and $d$. It also represents that Manhattan distance depends on the differences between the maximum and minimum sums $(s_{max}−s_{min})$ and the maximum and minimum differences $(d_{max}−d_{min})$.

Effect of removing a point: If we remove a point, it might affect these extreme values $(s_{min}, s_{max}, d_{min}, d_{max})$. To handle this:

1. Track the largest, second largest, smallest, and second smallest values for both $s$ and $d$.

2. Consider removing points that contribute to these extremes and recalculate the maximum distance.

So, the above two points unveil a key insight: only points contributing to the extreme values $(s_{min}, s_{max}, d_{min}, d_{max})$ need to be considered for removal. This limits the candidate points to at most four, ensuring an efficient approach rather than a brute-force method to check for all possible pairs.

Now, let’s look at the steps of the solution in detail:

1. We create variables, minSumIndex, maxSumIndex, minDiffIndex, maxDiffIndex, for storing the indexes of the points contributing to the smallest and largest sums $(s_{min}, s_{max})$ and differences $(d_{min}, d_{max})$.

2. We also create variables, minSum, minSum2nd, maxSum, maxSum2nd, minDiff, minDiff2nd, maxDiff, maxDiff2nd, to store the values of the smallest, second-smallest, largest, and second-largest sums and differences.

3. Create a variable, ans, to store the smallest possible value for the maximum distance.

4. We iterate through all points and for each point $(x, y)$:

   1. We create and compute variables:

      1. s$= x + y$ (sum of coordinates)

      2. d$=x - y$ (difference of coordinates)

   2. We also update both the smallest (minSum) and second smallest sums (minSum2nd) by checking:

      1. If s is smaller than the current smallest sum (minSum), update both the smallest and second smallest sums and their indexes:

         1. minSum = s

         2. minSum2nd = minSum

         3. minSumIndex = $\text{current index of the iteration}$

      2. If s is not the smallest but smaller than the second smallest(minSum2nd), update only the second smallest sum (minSum2nd):

         1. minSum2nd = s

   3. Next, we update both the maximum(maxSum) and second maximum sums (maxSum2nd) by checking:

      1. If s is larger than the current largest sum (maxSum), update both the largest and second-largest sums and their indexes:

         1. maxSum = s

         2. minSum2nd = maxSum

         3. minSumIndex = $\text{current index of the iteration}$

      2. If s is not the largest but is larger than the second smallest(maxSum2nd), update only the second-largest sum (maxSum2nd):

         1. maxSum2nd = s

   4. Similarly, we also update both the smallest(minDiff) and second smallest differences (minDiff2nd) by checking:

      1. If d is smaller than the current smallest difference (minDiff), update both the smallest and second-smallest differences and their indexes:

         1. minDiff = d

         2. minDiff2nd = minDiff

         3. minDiffIndex = $\text{current index of the iteration}$

      2. If d is not the smallest but smaller than the second-smallest (minDiff2nd), update only the second smallest difference (minDiff2nd):

         1. minDiff2nd = d

   5. Next, we update both the maximum(maxDiff) and second maximum differences (maxDiff2nd) by checking:

      1. If d is larger than the current largest difference (maxDiff), update both the largest and second largest difference and their indexes:

         1. maxDiff = d

         2. minDiff2nd = maxDiff

         3. minDiffIndex = $\text{current index of the iteration}$

      2. If d is not the largest but larger than the second smallest (maxDiff2nd), update only the second-largest difference (maxDiff2nd):

         1. maxDiff2nd = d

5. After iterating through the points array, we identify candidate points for removal (identify the indexes of points contributing to the extreme values): $(s_{min}, s_{max}, d_{min}, d_{max})$. These points are the only candidates for removal since their removal might affect the maximum Manhattan distance.

6. For identifying candidate points for removal, we iterate through each candidate point (from the extreme indexes(minSumIndex, maxSumIndex, minDiffIndex, maxDiffIndex)) and adjust the extreme values by evaluating them:

   1. If the current candidate point is the smallest sum (minSum), we use the second smallest sum (minSum2nd) as the adjusted minimum sum, adjMinSum, to calculate the minimum possible value for the Manhattan distance. Otherwise, we use minSum.

   2. If the current candidate point is the largest sum (maxSum), we use the second-largest sum (maxSum2nd) as the adjusted maximum sum, adjMaxSum, to calculate the minimum possible value for the Manhattan distance. Otherwise, we use maxSum.

   3. If the current candidate point is the smallest difference (minDiff), we use the second smallest difference (minDiff2nd) as the adjusted minimum difference, adjMinDiff, to calculate the minimum possible value for the Manhattan distance. Otherwise, we use minDiff.

   4. If the current candidate point is the largest difference (maxDiff), we use the second-largest difference (maxDiff2nd) as the adjusted maximum difference, adjMaxDiff, to calculate the minimum possible value for the Manhattan distance. Otherwise, we use maxDiff.

   5. After adjusting the candidate points, we compute the maximum Manhattan distance using the adjusted values:

      1. $distance=max(AdjMax​Sum−AdjMin​Sum,AdjMax​Diff−AdjMin​Diff)$

      2. We then update ans with the minimum of its current value and the computed $distance$.

7. After evaluating all candidate points, we return ans containing the smallest maximum Manhattan distance possible after removing one point.

Let’s look at the following illustration to get a better understanding of the solution: