Minimize Manhattan Distances solution and explanation
6 more videos on this problem
3102. Minimize Manhattan Distances | Max Manhattan Distance between Any Points | MathAryan Mittal · 26:33 · 8K views
3102. Minimize Manhattan Distances | Weekly Leetcode 391codingMohan · 25:13 · 1K views
3102. Minimize Manhattan Distances (Leetcode Hard)Programming Live with Larry · 55:16 · 786 views
Leetcode Weekly 391: Minimize Manhattan Distances | Ranked 114 - Brute Force to OptimisationsBharat Khanna · 21:23 · 522 views
3102. Minimize Manhattan Distances || Leetcode Weekly Contest 391Ashish Kumar · 16:13 · 364 views
LeetCode Hard 3102:Minimize Manhattan Distances(Beginner friendly explanation & implementation)Leetcode onii-chan · 24:46 · 258 views
3102. Minimize Manhattan Distances | 4 Approaches | Optimal O(n)Tech Courses · 28:03 · 235 views
The problem
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 <= 105points[i].length == 21 <= points[i][0], points[i][1] <= 108
Approach overview
Problem Overview: You are given points on a 2D grid. Remove exactly one point so that the maximum Manhattan distance between any remaining pair of points becomes as small as possible. The challenge is computing this efficiently without checking every pair after every removal.
Approach 1: Maximize and Minimize Projections (O(n) time, O(n) space)
The key observation comes from geometry: Manhattan distance |x1 - x2| + |y1 - y2| can be transformed using projections. If you define p = x + y and q = x - y, then the Manhattan distance between two points becomes the maximum difference across these projections. Instead of comparing every pair, compute the maximum and minimum values of p and q. The farthest pair must involve these extremes. To simulate removing a point, track the top two maxima and minima for both projections. When you remove a candidate point, recompute the distance using the second-best extremes if necessary. This avoids recomputing everything and reduces the problem to a single pass over the points. The result is an efficient linear-time solution that only stores projection values in arrays.
Approach 2: Pre-compute Maximum Distances (O(n log n) time, O(n) space)
Another approach keeps the projection values inside an ordered structure. Compute x+y and x-y for each point and store them in ordered containers or sorted arrays. These allow quick access to current minimum and maximum values. For every point, temporarily remove its projections from the structure, calculate the maximum Manhattan distance using the remaining extremes, and insert it back. The ordered container guarantees O(log n) updates and queries. This method is conceptually simpler if you already use sorting or ordered sets, though it is slightly slower than the linear projection trick.
Both strategies rely on the same geometric transformation but differ in how they maintain extremes. Instead of pairwise comparisons, the solution reduces the entire search space to just four critical values: max/min of x+y and max/min of x-y. This drastically cuts down the work required.
Recommended for interviews: The projection-based solution is the expected answer. It demonstrates understanding of Manhattan distance transformations and reduces the problem to an O(n) scan over the array of points. Showing the brute-force reasoning first helps justify the optimization, but interviewers typically look for the projection insight.
Approach 1: Approach 1: Maximize and Minimize Projections
To solve the problem optimally, we need to consider how removing each point affects the maximum possible Manhattan distance. Instead of calculating all distances, we can utilize the mathematical properties of the Manhattan Distance. Every Manhattan Distance can be transformed into the form of linear combinations of the coordinates:
distance(p1, p2) = |x1 - x2| + |y1 - y2| can be considered as a maximum of combinations of (x + y), (x - y), (-x + y), (-x - y) after evaluating all possible sign combinations.
This approach leverages projections of points based on x+y and x-y.
def minimize_max_manhattan(points):
if len(points) <= 3:
return 0
transformed = []
for (x, y) in points:
transformed.append((x + y, x - y))
min_values = [float('inf')] * 4
max_values = [float('-inf')] * 4
for (x_plus_y, x_minus_y) in transformed:
min_values[0] = min(min_values[0], x_plus_y)
max_values[0] = max(max_values[0], x_plus_y)
min_values[1] = min(min_values[1], x_minus_y)
max_values[1] = max(max_values[1], x_minus_y)
min_values[2] = min(min_values[2], -x_plus_y)
max_values[2] = max(max_values[2], -x_plus_y)
min_values[3] = min(min_values[3], -x_minus_y)
max_values[3] = max(max_values[3], -x_minus_y)
initial_max_distance = max(max_values[i] - min_values[i] for i in range(4))
result = float('inf')
for (x, y) in points:
reduce_x_plus_y = x + y
reduce_x_minus_y = x - y
current_max_distance = 0
for i in range(4):
diff_min = 0 if reduce_x_plus_y == min_values[i] else max_values[i] - min_values[i]
diff_max = 0 if reduce_x_plus_y == max_values[i] else max_values[i] - min_values[i]
current_max_distance = max(current_max_distance, max(diff_min, diff_max))
result = min(result, current_max_distance)
return result#include <vector>
#include <algorithm>
#include <climits>
int minimizeMaxManhattan(std::vector<std::vector<int>>& points) {
if (points.size() <= 3)
return 0;
std::vector<int> transformed_plus,
transformed_minus;
for (auto &p : points) {
int x = p[0], y = p[1];
transformed_plus.push_back(x + y);
transformed_minus.push_back(x - y);
}
int min_plus = *std::min_element(transformed_plus.begin(), transformed_plus.end());
int max_plus = *std::max_element(transformed_plus.begin(), transformed_plus.end());
int min_minus = *std::min_element(transformed_minus.begin(), transformed_minus.end());
int max_minus = *std::max_element(transformed_minus.begin(), transformed_minus.end());
int initial_max_distance = std::max(max_plus - min_plus, max_minus - min_minus);
int result = INT_MAX;
for (auto &p : points) {
int x = p[0], y = p[1];
int reduced_plus = x + y;
int reduced_minus = x - y;
int current_max_distance = 0;
current_max_distance = std::max({
current_max_distance,
std::max(max_plus - reduced_plus, reduced_plus - min_plus),
std::max(max_minus - reduced_minus, reduced_minus - min_minus)
});
result = std::min(result, current_max_distance);
}
return result;
}The algorithm utilizes a transformation of the points:
- Calculate transformed coordinates for each point using combinations of x+y and x-y.
- Track minimal and maximal transformed projections.
- Calculate the initial maximum distance based on projections.
- Attempt to minimize the maximum distance by removing each point and recomputing the effective maximum Manhattan distance across the remaining points.
Time Complexity: O(n) due to linear scans for projections and computations.
Space Complexity: O(n) for transformed list storage.
Approach 2: Approach 2: Pre-compute Maximum Distances
A second approach involves computing the maximum Manhattan distance upfront and checking for reductions possible by removing one point. You accumulate results in an array or vector for precomputed distances.
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int MinimizeMaxManhattan(int[][] points) {
if (points.Length <= 3)
return 0;
List<int> transformedPlus = new List<int>();
List<int> transformedMinus = new List<int>();
foreach (var p in points) {
int x = p[0], y = p[1];
transformedPlus.Add(x + y);
transformedMinus.Add(x - y);
}
int minPlus = transformedPlus.Min();
int maxPlus = transformedPlus.Max();
int minMinus = transformedMinus.Min();
int maxMinus = transformedMinus.Max();
int initialMaxDistance = Math.Max(maxPlus - minPlus, maxMinus - minMinus);
int result = int.MaxValue;
foreach (var p in points) {
int x = p[0], y = p[1];
int reducedPlus = x + y;
int reducedMinus = x - y;
int currentMaxDistance = Math.Max(Math.Max(maxPlus - reducedPlus, reducedPlus - minPlus),
Math.Max(maxMinus - reducedMinus, reducedMinus - minMinus));
result = Math.Min(result, currentMaxDistance);
}
return result;
}
}This approach involves iteration with precomputation:
- Track and transform input points to an intermediate form, as described.
- Initialize metadata for minimal and maximal transformed values.
- Iterate through the array, determining possible reductions in the largest Manhattan boundary through projected difference computations.
Time Complexity: O(n) similar to previous approach for a full iteration.
Space Complexity: O(n) for list usage.
Approach 3: Ordered Set
For two points (x_1, y_1) and (x_2, y_2), their Manhattan distance is |x_1 - x_2| + |y_1 - y_2|. We can transform it into max(x_1 - x_2, x_2 - x_1) + max(y_1 - y_2, y_2 - y_1), which is:
$
|x_1 - x_2| + |y_1 - y_2| = max \begin{cases}
x_1 - x_2 + y_1 - y_2 \
x_2 - x_1 + y_2 - y_1 \
x_1 - x_2 + y_2 - y_1 \
x_2 - x_1 + y_1 - y_2
\end{cases}
This can be simplified to:
|x_1 - x_2| + |y_1 - y_2| = max \begin{cases}
(x_1 + y_1) - (x_2 + y_2) \
(x_2 + y_2) - (x_1 + y_1) \
(x_1 - y_1) - (x_2 - y_2) \
(x_2 - y_2) - (x_1 - y_1)
\end{cases}
Here, the first two cases can be represented as max(max(x_1 + y_1, x_2 + y_2) - min(x_1 + y_1, x_2 + y_2)), and the last two cases can be represented as max(max(x_1 - y_1, x_2 - y_2) - min(x_1 - y_1, x_2 - y_2)).
Therefore, we can store all points according to the values of x + y and x - y in two ordered sets, respectively. Then, for each point, we remove it, update the values in the ordered sets, calculate the difference between the maximum and minimum values, and take the minimum value.
The time complexity is O(n log n), and the space complexity is O(n). Here, n$ is the number of points.
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;
}
}function minimumDistance(points: number[][]): number {
const st1 = new TreapMultiSet<number>();
const st2 = new TreapMultiSet<number>();
for (const [x, y] of points) {
st1.add(x + y);
st2.add(x - y);
}
let ans = Infinity;
for (const [x, y] of points) {
st1.delete(x + y);
st2.delete(x - y);
ans = Math.min(ans, Math.max(st1.last() - st1.first(), st2.last() - st2.first()));
st1.add(x + y);
st2.add(x - y);
}
return ans;
}
type CompareFunction<T, R extends 'number' | 'boolean'> = (
a: T,
b: T,
) => R extends 'number' ? number : boolean;
interface ITreapMultiSet<T> extends Iterable<T> {
add: (...value: T[]) => this;
has: (value: T) => boolean;
delete: (value: T) => void;
bisectLeft: (value: T) => number;
bisectRight: (value: T) => number;
indexOf: (value: T) => number;
lastIndexOf: (value: T) => number;
at: (index: number) => T | undefined;
first: () => T | undefined;
last: () => T | undefined;
lower: (value: T) => T | undefined;
higher: (value: T) => T | undefined;
floor: (value: T) => T | undefined;
ceil: (value: T) => T | undefined;
shift: () => T | undefined;
pop: (index?: number) => T | undefined;
count: (value: T) => number;
keys: () => IterableIterator<T>;
values: () => IterableIterator<T>;
rvalues: () => IterableIterator<T>;
entries: () => IterableIterator<[number, T]>;
readonly size: number;
}
class TreapNode<T = number> {
value: T;
count: number;
size: number;
priority: number;
left: TreapNode<T> | null;
right: TreapNode<T> | null;
constructor(value: T) {
this.value = value;
this.count = 1;
this.size = 1;
this.priority = Math.random();
this.left = null;
this.right = null;
}
static getSize(node: TreapNode<any> | null): number {
return node?.size ?? 0;
}
static getFac(node: TreapNode<any> | null): number {
return node?.priority ?? 0;
}
pushUp(): void {
let tmp = this.count;
tmp += TreapNode.getSize(this.left);
tmp += TreapNode.getSize(this.right);
this.size = tmp;
}
rotateRight(): TreapNode<T> {
// eslint-disable-next-line @typescript-eslint/no-this-alias
let node: TreapNode<T> = this;
const left = node.left;
node.left = left?.right ?? null;
left && (left.right = node);
left && (node = left);
node.right?.pushUp();
node.pushUp();
return node;
}
rotateLeft(): TreapNode<T> {
// eslint-disable-next-line @typescript-eslint/no-this-alias
let node: TreapNode<T> = this;
const right = node.right;
node.right = right?.left ?? null;
right && (right.left = node);
right && (node = right);
node.left?.pushUp();
node.pushUp();
return node;
}
}
class TreapMultiSet<T = number> implements ITreapMultiSet<T> {
private readonly root: TreapNode<T>;
private readonly compareFn: CompareFunction<T, 'number'>;
private readonly leftBound: T;
private readonly rightBound: T;
constructor(compareFn?: CompareFunction<T, 'number'>);
constructor(compareFn: CompareFunction<T, 'number'>, leftBound: T, rightBound: T);
constructor(
compareFn: CompareFunction<T, any> = (a: any, b: any) => a - b,
leftBound: any = -Infinity,
rightBound: any = Infinity,
) {
this.root = new TreapNode<T>(rightBound);
this.root.priority = Infinity;
this.root.left = new TreapNode<T>(leftBound);
this.root.left.priority = -Infinity;
this.root.pushUp();
this.leftBound = leftBound;
this.rightBound = rightBound;
this.compareFn = compareFn;
}
get size(): number {
return this.root.size - 2;
}
get height(): number {
const getHeight = (node: TreapNode<T> | null): number => {
if (node == null) return 0;
return 1 + Math.max(getHeight(node.left), getHeight(node.right));
};
return getHeight(this.root);
}
/**
*
* @complexity `O(logn)`
* @description Returns true if value is a member.
*/
has(value: T): boolean {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): boolean => {
if (node == null) return false;
if (compare(node.value, value) === 0) return true;
if (compare(node.value, value) < 0) return dfs(node.right, value);
return dfs(node.left, value);
};
return dfs(this.root, value);
}
/**
*
* @complexity `O(logn)`
* @description Add value to sorted set.
*/
add(...values: T[]): this {
const compare = this.compareFn;
const dfs = (
node: TreapNode<T> | null,
value: T,
parent: TreapNode<T>,
direction: 'left' | 'right',
): void => {
if (node == null) return;
if (compare(node.value, value) === 0) {
node.count++;
node.pushUp();
} else if (compare(node.value, value) > 0) {
if (node.left) {
dfs(node.left, value, node, 'left');
} else {
node.left = new TreapNode(value);
node.pushUp();
}
if (TreapNode.getFac(node.left) > node.priority) {
parent[direction] = node.rotateRight();
}
} else if (compare(node.value, value) < 0) {
if (node.right) {
dfs(node.right, value, node, 'right');
} else {
node.right = new TreapNode(value);
node.pushUp();
}
if (TreapNode.getFac(node.right) > node.priority) {
parent[direction] = node.rotateLeft();
}
}
parent.pushUp();
};
values.forEach(value => dfs(this.root.left, value, this.root, 'left'));
return this;
}
/**
*
* @complexity `O(logn)`
* @description Remove value from sorted set if it is a member.
* If value is not a member, do nothing.
*/
delete(value: T): void {
const compare = this.compareFn;
const dfs = (
node: TreapNode<T> | null,
value: T,
parent: TreapNode<T>,
direction: 'left' | 'right',
): void => {
if (node == null) return;
if (compare(node.value, value) === 0) {
if (node.count > 1) {
node.count--;
node?.pushUp();
} else if (node.left == null && node.right == null) {
parent[direction] = null;
} else {
// 旋到根节点
if (
node.right == null ||
TreapNode.getFac(node.left) > TreapNode.getFac(node.right)
) {
parent[direction] = node.rotateRight();
dfs(parent[direction]?.right ?? null, value, parent[direction]!, 'right');
} else {
parent[direction] = node.rotateLeft();
dfs(parent[direction]?.left ?? null, value, parent[direction]!, 'left');
}
}
} else if (compare(node.value, value) > 0) {
dfs(node.left, value, node, 'left');
} else if (compare(node.value, value) < 0) {
dfs(node.right, value, node, 'right');
}
parent?.pushUp();
};
dfs(this.root.left, value, this.root, 'left');
}
/**
*
* @complexity `O(logn)`
* @description Returns an index to insert value in the sorted set.
* If the value is already present, the insertion point will be before (to the left of) any existing values.
*/
bisectLeft(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
return TreapNode.getSize(node.left);
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
return dfs(this.root, value) - 1;
}
/**
*
* @complexity `O(logn)`
* @description Returns an index to insert value in the sorted set.
* If the value is already present, the insertion point will be before (to the right of) any existing values.
*/
bisectRight(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
return TreapNode.getSize(node.left) + node.count;
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
return dfs(this.root, value) - 1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the index of the first occurrence of a value in the set, or -1 if it is not present.
*/
indexOf(value: T): number {
const compare = this.compareFn;
let isExist = false;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
isExist = true;
return TreapNode.getSize(node.left);
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
const res = dfs(this.root, value) - 1;
return isExist ? res : -1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the index of the last occurrence of a value in the set, or -1 if it is not present.
*/
lastIndexOf(value: T): number {
const compare = this.compareFn;
let isExist = false;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) {
isExist = true;
return TreapNode.getSize(node.left) + node.count - 1;
} else if (compare(node.value, value) > 0) {
return dfs(node.left, value);
} else if (compare(node.value, value) < 0) {
return dfs(node.right, value) + TreapNode.getSize(node.left) + node.count;
}
return 0;
};
const res = dfs(this.root, value) - 1;
return isExist ? res : -1;
}
/**
*
* @complexity `O(logn)`
* @description Returns the item located at the specified index.
* @param index The zero-based index of the desired code unit. A negative index will count back from the last item.
*/
at(index: number): T | undefined {
if (index < 0) index += this.size;
if (index < 0 || index >= this.size) return undefined;
const dfs = (node: TreapNode<T> | null, rank: number): T | undefined => {
if (node == null) return undefined;
if (TreapNode.getSize(node.left) >= rank) {
return dfs(node.left, rank);
} else if (TreapNode.getSize(node.left) + node.count >= rank) {
return node.value;
} else {
return dfs(node.right, rank - TreapNode.getSize(node.left) - node.count);
}
};
const res = dfs(this.root, index + 2);
return ([this.leftBound, this.rightBound] as any[]).includes(res) ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element less than `val`, return `undefined` if no such element found.
*/
lower(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) >= 0) return dfs(node.left, value);
const tmp = dfs(node.right, value);
if (tmp == null || compare(node.value, tmp) > 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.leftBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element greater than `val`, return `undefined` if no such element found.
*/
higher(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) <= 0) return dfs(node.right, value);
const tmp = dfs(node.left, value);
if (tmp == null || compare(node.value, tmp) < 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.rightBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element less than or equal to `val`, return `undefined` if no such element found.
*/
floor(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) === 0) return node.value;
if (compare(node.value, value) >= 0) return dfs(node.left, value);
const tmp = dfs(node.right, value);
if (tmp == null || compare(node.value, tmp) > 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.leftBound ? undefined : res;
}
/**
*
* @complexity `O(logn)`
* @description Find and return the element greater than or equal to `val`, return `undefined` if no such element found.
*/
ceil(value: T): T | undefined {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): T | undefined => {
if (node == null) return undefined;
if (compare(node.value, value) === 0) return node.value;
if (compare(node.value, value) <= 0) return dfs(node.right, value);
const tmp = dfs(node.left, value);
if (tmp == null || compare(node.value, tmp) < 0) {
return node.value;
} else {
return tmp;
}
};
const res = dfs(this.root, value) as any;
return res === this.rightBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Returns the last element from set.
* If the set is empty, undefined is returned.
*/
first(): T | undefined {
const iter = this.inOrder();
iter.next();
const res = iter.next().value;
return res === this.rightBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Returns the last element from set.
* If the set is empty, undefined is returned .
*/
last(): T | undefined {
const iter = this.reverseInOrder();
iter.next();
const res = iter.next().value;
return res === this.leftBound ? undefined : res;
}
/**
* @complexity `O(logn)`
* @description
* Removes the first element from an set and returns it.
* If the set is empty, undefined is returned and the set is not modified.
*/
shift(): T | undefined {
const first = this.first();
if (first === undefined) return undefined;
this.delete(first);
return first;
}
/**
* @complexity `O(logn)`
* @description
* Removes the last element from an set and returns it.
* If the set is empty, undefined is returned and the set is not modified.
*/
pop(index?: number): T | undefined {
if (index == null) {
const last = this.last();
if (last === undefined) return undefined;
this.delete(last);
return last;
}
const toDelete = this.at(index);
if (toDelete == null) return;
this.delete(toDelete);
return toDelete;
}
/**
*
* @complexity `O(logn)`
* @description
* Returns number of occurrences of value in the sorted set.
*/
count(value: T): number {
const compare = this.compareFn;
const dfs = (node: TreapNode<T> | null, value: T): number => {
if (node == null) return 0;
if (compare(node.value, value) === 0) return node.count;
if (compare(node.value, value) < 0) return dfs(node.right, value);
return dfs(node.left, value);
};
return dfs(this.root, value);
}
*[Symbol.iterator](): Generator<T, any, any> {
yield* this.values();
}
/**
* @description
* Returns an iterable of keys in the set.
*/
*keys(): Generator<T, any, any> {
yield* this.values();
}
/**
* @description
* Returns an iterable of values in the set.
*/
*values(): Generator<T, any, any> {
const iter = this.inOrder();
iter.next();
const steps = this.size;
for (let _ = 0; _ < steps; _++) {
yield iter.next().value;
}
}
/**
* @description
* Returns a generator for reversed order traversing the set.
*/
*rvalues(): Generator<T, any, any> {
const iter = this.reverseInOrder();
iter.next();
const steps = this.size;
for (let _ = 0; _ < steps; _++) {
yield iter.next().value;
}
}
/**
* @description
* Returns an iterable of key, value pairs for every entry in the set.
*/
*entries(): IterableIterator<[number, T]> {
const iter = this.inOrder();
iter.next();
const steps = this.size;
for (let i = 0; i < steps; i++) {
yield [i, iter.next().value];
}
}
private *inOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
if (root == null) return;
yield* this.inOrder(root.left);
const count = root.count;
for (let _ = 0; _ < count; _++) {
yield root.value;
}
yield* this.inOrder(root.right);
}
private *reverseInOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> {
if (root == null) return;
yield* this.reverseInOrder(root.right);
const count = root.count;
for (let _ = 0; _ < count; _++) {
yield root.value;
}
yield* this.reverseInOrder(root.left);
}
}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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Maximize and Minimize Projections | Time Complexity: O(n) due to linear scans for projections and computations. |
| Approach 2: Pre-compute Maximum Distances | Time Complexity: O(n) similar to previous approach for a full iteration. |
| Ordered Set | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Maximize and Minimize Projections | O(n) | O(n) | Best general solution. Uses (x+y) and (x-y) projections to track extremes efficiently. |
| Pre-compute Maximum Distances with Ordered Structure | O(n log n) | O(n) | Useful when working with sorted containers or ordered sets where insertion/removal is needed. |
Frequently asked questions
Is Minimize Manhattan Distances easy or hard?
Minimize Manhattan Distances is classified as a Hard problem because it requires recognizing the geometric projection trick. A brute force approach is straightforward but too slow, while the optimal solution depends on transforming coordinates and tracking extreme values efficiently.
Minimize Manhattan Distances Python/Java solution
Python and C++ implementations typically compute x+y and x-y arrays and track the largest and smallest values with indices. During iteration, the algorithm checks how removing a point affects the extreme projections. The same logic can be implemented in Java, C++, Python, or C# with linear time complexity.
How to solve Minimize Manhattan Distances in O(n)?
Transform each point (x, y) into two projections: p = x + y and q = x - y. Track the largest and smallest values for both projections along with their second extremes. For each candidate removal, recompute the maximum difference using the remaining extremes. This avoids pairwise comparisons and keeps the algorithm linear.
What is the best approach for Minimize Manhattan Distances?
The optimal approach uses projection transformations with (x+y) and (x-y). By tracking the maximum and minimum values of these projections, you can identify the farthest Manhattan distances without comparing all pairs. Maintaining the top two extremes allows simulating removal of each point in O(n) total time.
Is Minimize Manhattan Distances asked at Google/Amazon/Meta?
Manhattan distance transformation problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving coordinate projections, geometry optimization, and extreme value tracking are common in senior-level algorithm rounds.
What data structure is used in Minimize Manhattan Distances?
Most efficient solutions use arrays to store projection values and track extreme elements. Some implementations use ordered sets or balanced trees to maintain sorted projections dynamically while removing and reinserting points.
What is the time complexity of Minimize Manhattan Distances?
The optimal projection-based solution runs in O(n) time and O(n) space. It scans all points once to compute projections and track extreme values. Alternative solutions using ordered sets or sorted containers typically run in O(n log n).