Welcome to Subscribe On Youtube
3102. Minimize Manhattan Distances
Description
You are given a 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 0th point the maximum distance is between points (5, 15) and (10, 2), which is
\|5 - 10\| + \|15 - 2\| = 18
. - After removing the 1st point the maximum distance is between points (3, 10) and (10, 2), which is
\|3 - 10\| + \|10 - 2\| = 15
. - After removing the 2nd point the maximum distance is between points (5, 15) and (4, 4), which is
\|5 - 4\| + \|15 - 4\| = 12
. - After removing the 3rd 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 1
-
class Solution { public int minimumDistance(int[][] points) { TreeMap<Integer, Integer> tm1 = new TreeMap<>(); TreeMap<Integer, Integer> tm2 = new TreeMap<>(); for (int[] p : points) { int x = p[0], y = p[1]; tm1.merge(x + y, 1, Integer::sum); tm2.merge(x - y, 1, Integer::sum); } int ans = Integer.MAX_VALUE; for (int[] p : points) { int x = p[0], y = p[1]; if (tm1.merge(x + y, -1, Integer::sum) == 0) { tm1.remove(x + y); } if (tm2.merge(x - y, -1, Integer::sum) == 0) { tm2.remove(x - y); } ans = Math.min( ans, Math.max(tm1.lastKey() - tm1.firstKey(), tm2.lastKey() - tm2.firstKey())); tm1.merge(x + y, 1, Integer::sum); tm2.merge(x - y, 1, Integer::sum); } return ans; } }
-
class Solution { public: int minimumDistance(vector<vector<int>>& points) { multiset<int> st1; multiset<int> st2; for (auto& p : points) { int x = p[0], y = p[1]; st1.insert(x + y); st2.insert(x - y); } int ans = INT_MAX; for (auto& p : points) { int x = p[0], y = p[1]; st1.erase(st1.find(x + y)); st2.erase(st2.find(x - y)); ans = min(ans, max(*st1.rbegin() - *st1.begin(), *st2.rbegin() - *st2.begin())); st1.insert(x + y); st2.insert(x - y); } return ans; } };
-
from sortedcontainers import SortedList class Solution: def minimumDistance(self, points: List[List[int]]) -> int: sl1 = SortedList() sl2 = SortedList() for x, y in points: sl1.add(x + y) sl2.add(x - y) ans = inf for x, y in points: sl1.remove(x + y) sl2.remove(x - y) ans = min(ans, max(sl1[-1] - sl1[0], sl2[-1] - sl2[0])) sl1.add(x + y) sl2.add(x - y) return ans
-
func minimumDistance(points [][]int) int { st1 := redblacktree.New[int, int]() st2 := redblacktree.New[int, int]() merge := func(st *redblacktree.Tree[int, int], x, v int) { c, _ := st.Get(x) if c+v == 0 { st.Remove(x) } else { st.Put(x, c+v) } } for _, p := range points { x, y := p[0], p[1] merge(st1, x+y, 1) merge(st2, x-y, 1) } ans := math.MaxInt for _, p := range points { x, y := p[0], p[1] merge(st1, x+y, -1) merge(st2, x-y, -1) ans = min(ans, max(st1.Right().Key-st1.Left().Key, st2.Right().Key-st2.Left().Key)) merge(st1, x+y, 1) merge(st2, x-y, 1) } return ans }