3102. Minimize Manhattan Distances

Problem Link

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 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 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

Solution

---

Python3

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        N = len(points)
        # maxManhattanDistance = max(max(abs(si - sj), abs(di - dj)))
 
        def manhattan(i, j):
            return abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
        
        def maxManhattanDistance(skip = -1):
            maxSum, minSum, maxDiff, minDiff = -inf, inf, -inf, inf
            maxSumIndex = minSumIndex = maxDiffIndex = minDiffIndex = -1
 
            for i in range(N):
                if i == skip: continue
 
                s = points[i][0] + points[i][1]
                d = points[i][0] - points[i][1]
 
                if s > maxSum:
                    maxSum = s
                    maxSumIndex = i
                
                if s < minSum:
                    minSum = s
                    minSumIndex = i
                
                if d > maxDiff:
                    maxDiff = d
                    maxDiffIndex = i
                
                if d < minDiff:
                    minDiff = d
                    minDiffIndex = i
                
            maxDistance = max(maxSum - minSum, maxDiff - minDiff)
            if maxDistance == (maxSum - minSum):
                return (maxSumIndex, minSumIndex)
            
            return (maxDiffIndex, minDiffIndex)
        
        mi, mj = maxManhattanDistance()
        mi1, mj1 = maxManhattanDistance(mi)
        mi2, mj2 = maxManhattanDistance(mj)
 
        return min(manhattan(mi, mj), manhattan(mi1, mj1), manhattan(mi2, mj2))