Skip to content

3102. Minimize Manhattan Distances 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
 public:
  int minimumDistance(vector<vector<int>>& points) {
    const auto [i, j] = maxManhattanDistance(points, -1);
    const auto [xi, yi] = maxManhattanDistance(points, i);
    const auto [xj, yj] = maxManhattanDistance(points, j);
    return min(manhattan(points, xi, yi), manhattan(points, xj, yj));
  }

 private:
  // Returns the pair of indices a and b where points[a] and points[b] have the
  // maximum Manhattan distance and a != excludedIndex and b != excludedIndex.
  pair<int, int> maxManhattanDistance(const vector<vector<int>>& points,
                                      int excludedIndex) {
    int minSum = INT_MAX;
    int maxSum = INT_MIN;
    int minDiff = INT_MAX;
    int maxDiff = INT_MIN;
    int minSumIndex = -1;
    int maxSumIndex = -1;
    int minDiffIndex = -1;
    int maxDiffIndex = -1;

    for (int i = 0; i < points.size(); ++i) {
      if (i == excludedIndex)
        continue;
      const int x = points[i][0];
      const int y = points[i][1];
      const int sum = x + y;
      const int diff = x - y;
      if (sum < minSum)
        minSum = sum, minSumIndex = i;
      if (sum > maxSum)
        maxSum = sum, maxSumIndex = i;
      if (diff < minDiff)
        minDiff = diff, minDiffIndex = i;
      if (diff > maxDiff)
        maxDiff = diff, maxDiffIndex = i;
    }

    return maxSum - minSum >= maxDiff - minDiff
               ? pair<int, int>(minSumIndex, maxSumIndex)
               : pair<int, int>(minDiffIndex, maxDiffIndex);
  }

  int manhattan(const vector<vector<int>>& points, int i, int j) {
    return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
  public int minimumDistance(int[][] points) {
    final int[] maxIndices = maxManhattanDistance(points, -1);
    final int[] xiyi = maxManhattanDistance(points, maxIndices[0]);
    final int[] xjyj = maxManhattanDistance(points, maxIndices[1]);
    return Math.min(manhattan(points, xiyi[0], xiyi[1]), //
                    manhattan(points, xjyj[0], xjyj[1]));
  }

  // Returns the pair of indices a and b where points[a] and points[b] have the
  // maximum Manhattan distance and a != excludedIndex and b != excludedIndex.
  private int[] maxManhattanDistance(int[][] points, int excludedIndex) {
    int minSum = Integer.MAX_VALUE;
    int maxSum = Integer.MIN_VALUE;
    int minDiff = Integer.MAX_VALUE;
    int maxDiff = Integer.MIN_VALUE;
    int minSumIndex = -1;
    int maxSumIndex = -1;
    int minDiffIndex = -1;
    int maxDiffIndex = -1;

    for (int i = 0; i < points.length; ++i) {
      if (i == excludedIndex)
        continue;
      final int x = points[i][0];
      final int y = points[i][1];
      final int sum = x + y;
      final int diff = x - y;
      if (sum < minSum) {
        minSum = sum;
        minSumIndex = i;
      }
      if (sum > maxSum) {
        maxSum = sum;
        maxSumIndex = i;
      }
      if (diff < minDiff) {
        minDiff = diff;
        minDiffIndex = i;
      }
      if (diff > maxDiff) {
        maxDiff = diff;
        maxDiffIndex = i;
      }
    }

    return maxSum - minSum >= maxDiff - minDiff ? new int[] {minSumIndex, maxSumIndex}
                                                : new int[] {minDiffIndex, maxDiffIndex};
  }

  private int manhattan(int[][] points, int i, int j) {
    return Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution:
  def minimumDistance(self, points: list[list[int]]) -> int:
    i, j = self._maxManhattanDistance(points, -1)
    xi, yi = self._maxManhattanDistance(points, i)
    xj, yj = self._maxManhattanDistance(points, j)
    return min(self._manhattan(points, xi, yi),
               self._manhattan(points, xj, yj))

  def _maxManhattanDistance(
      self,
      points: list[list[int]],
      excludedIndex: int,
  ) -> int:
    minSum = math.inf
    maxSum = -math.inf
    minDiff = math.inf
    maxDiff = -math.inf
    minSumIndex = -1
    maxSumIndex = -1
    minDiffIndex = -1
    maxDiffIndex = -1

    for i, (x, y) in enumerate(points):
      if i == excludedIndex:
        continue
      summ = x + y
      diff = x - y
      if summ < minSum:
        minSum = summ
        minSumIndex = i
      if summ > maxSum:
        maxSum = summ
        maxSumIndex = i
      if diff < minDiff:
        minDiff = diff
        minDiffIndex = i
      if diff > maxDiff:
        maxDiff = diff
        maxDiffIndex = i

    return ([minSumIndex, maxSumIndex] if maxSum - minSum >= maxDiff - minDiff
            else [minDiffIndex, maxDiffIndex])

  def _manhattan(self, points: list[list[int]], i: int, j: int) -> int:
    return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])