3102. Minimize Manhattan Distances

Description

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 .

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 0^th point the maximum distance is between points (5, 15) and (10, 2), which is |5 - 10| + |15 - 2| = 18.
• After removing the 1^st point the maximum distance is between points (3, 10) and (10, 2), which is |3 - 10| + |10 - 2| = 15.
• After removing the 2^nd point the maximum distance is between points (5, 15) and (4, 4), which is |5 - 4| + |15 - 4| = 12.
• After removing the 3^rd 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

 

Solutions

Solution: Math

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[][]} points
 * @return {number}
 */
const minimumDistance = function (points) {
  const n = points.length;

  const getMaxManhattanDistance = (excludedIndex = -1) => {
    let maxSum = Number.MIN_SAFE_INTEGER;
    let minSum = Number.MAX_SAFE_INTEGER;
    let maxDiff = Number.MIN_SAFE_INTEGER;
    let minDiff = Number.MAX_SAFE_INTEGER;
    let maxSumIndex = -1;
    let minSumIndex = -1;
    let maxDiffIndex = -1;
    let minDiffIndex = -1;

    for (let index = 0; index < n; index++) {
      if (index === excludedIndex) continue;

      const [x, y] = points[index];
      const sum = x + y;
      const diff = x - y;

      if (sum > maxSum) {
        maxSum = sum;
        maxSumIndex = index;
      }

      if (sum < minSum) {
        minSum = sum;
        minSumIndex = index;
      }

      if (diff > maxDiff) {
        maxDiff = diff;
        maxDiffIndex = index;
      }

      if (diff < minDiff) {
        minDiff = diff;
        minDiffIndex = index;
      }
    }

    if (maxSum - minSum > maxDiff - minDiff) {
      return [minSumIndex, maxSumIndex];
    }

    return [minDiffIndex, maxDiffIndex];
  };

  const manhattan = (a, b) => {
    const [x1, y1] = points[a];
    const [x2, y2] = points[b];

    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
  };

  const [excludedA, excludedB] = getMaxManhattanDistance();
  const [a, b] = getMaxManhattanDistance(excludedA);
  const [c, d] = getMaxManhattanDistance(excludedB);

  return Math.min(manhattan(a, b), manhattan(c, d));
};