3102. Minimize Manhattan Distances LeetCode Solution
In this guide, you will get 3102. Minimize Manhattan Distances LeetCode Solution with the best time and space complexity. The solution to Minimize Manhattan Distances problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Minimize Manhattan Distances solution in C++
- Minimize Manhattan Distances solution in Java
- Minimize Manhattan Distances solution in Python
- Additional Resources
Problem Statement of Minimize Manhattan Distances
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 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
Complexity Analysis
- Time Complexity: O(n)
- Space Complexity: O(1)
3102. Minimize Manhattan Distances LeetCode Solution in C++
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]);
}
};
/* code provided by PROGIEZ */3102. Minimize Manhattan Distances LeetCode Solution in Java
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]);
}
}
// code provided by PROGIEZ3102. Minimize Manhattan Distances LeetCode Solution in Python
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])
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.