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∣$ ...