3102. Minimize Manhattan Distances

Problem Description

You are given an array points containing integer coordinates of points on a 2D plane, where each point is represented as points[i] = [xi, yi].

The distance between any two points is calculated using the Manhattan distance formula: |x1 - x2| + |y1 - y2|.

Your task is to find the minimum possible value of the maximum distance between any two points after removing exactly one point from the array.

In other words:

You must remove exactly one point from the given set of points
After removal, calculate all pairwise Manhattan distances between the remaining points
Find the maximum distance among all these pairs
Return the minimum possible value of this maximum distance across all possible choices of which point to remove

For example, if you have points A, B, C, and D, you would:

Try removing A, then find the max distance among pairs (B,C), (B,D), (C,D)
Try removing B, then find the max distance among pairs (A,C), (A,D), (C,D)
Try removing C, then find the max distance among pairs (A,B), (A,D), (B,D)
Try removing D, then find the max distance among pairs (A,B), (A,C), (B,C)
Return the minimum of all these maximum distances

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key insight is recognizing that calculating Manhattan distances between all pairs of points after removing each point would be inefficient. Instead, we need to understand what determines the maximum Manhattan distance in a set of points.

The Manhattan distance |x1 - x2| + |y1 - y2| can be rewritten by considering all possible sign combinations. Through algebraic manipulation, we can express this as:

max((x1 + y1) - (x2 + y2), (x2 + y2) - (x1 + y1), (x1 - y1) - (x2 - y2), (x2 - y2) - (x1 - y1))

This reveals that the Manhattan distance between two points depends on two transformed coordinates:

The sum x + y
The difference x - y

The maximum Manhattan distance in a set of points will be determined by either:

The difference between the maximum and minimum values of x + y across all points
The difference between the maximum and minimum values of x - y across all points

This transformation is powerful because instead of comparing all pairs of points, we only need to track the extremes (maximum and minimum) of these two transformed values.

When we remove a point, we're essentially asking: "How does removing this point affect the range of x + y values and the range of x - y values?" If the removed point was one of the extremes, the maximum distance might decrease. If it wasn't an extreme point, removing it won't affect the maximum distance at all.

By maintaining sorted lists of x + y and x - y values for all points, we can efficiently:

Remove a point from both lists
Check the new maximum distance (which is the max of the two ranges)
Add the point back
Try the next point

This approach transforms an O(n³) brute force solution into an O(n log n) solution using ordered sets.

Learn more about Math and Sorting patterns.

Solution Implementation

1class Solution: 2 def minimumDistance(self, points: List[List[int]]) -> int: 3 # Manhattan distance between two points (x1, y1) and (x2, y2) is |x1-x2| + |y1-y2| 4 # This can be rewritten as max(|(x1+y1) - (x2+y2)|, |(x1-y1) - (x2-y2)|) 5 # So we track x+y and x-y values for all points 6 7 # SortedList to maintain sorted order of x+y values 8 sum_sorted = SortedList() 9 # SortedList to maintain sorted order of x-y values  10 diff_sorted = SortedList() 11 12 # Add all points' transformed coordinates to the sorted lists 13 for x, y in points: 14 sum_sorted.add(x + y) 15 diff_sorted.add(x - y) 16 17 # Initialize answer to infinity 18 min_max_distance = float('inf') 19 20 # Try removing each point one by one 21 for x, y in points: 22 # Remove current point from both sorted lists 23 sum_sorted.remove(x + y) 24 diff_sorted.remove(x - y) 25 26 # Calculate maximum Manhattan distance among remaining points 27 # The maximum distance is the max of the ranges in both transformed dimensions 28 max_distance = max(sum_sorted[-1] - sum_sorted[0], 29 diff_sorted[-1] - diff_sorted[0]) 30 31 # Update minimum of maximum distances 32 min_max_distance = min(min_max_distance, max_distance) 33 34 # Add the point back for the next iteration 35 sum_sorted.add(x + y) 36 diff_sorted.add(x - y) 37 38 return min_max_distance 39

1class Solution { 2 public int minimumDistance(int[][] points) { 3 // Transform coordinates to simplify Manhattan distance calculation 4 // For points (x1,y1) and (x2,y2), Manhattan distance |x1-x2| + |y1-y2| 5 // can be expressed as max(|(x1+y1)-(x2+y2)|, |(x1-y1)-(x2-y2)|) 6 7 // TreeMaps to maintain sorted order of transformed coordinates 8 // Key: transformed coordinate value, Value: count of points with this value 9 TreeMap<Integer, Integer> sumCoordinates = new TreeMap<>(); // stores x+y values 10 TreeMap<Integer, Integer> diffCoordinates = new TreeMap<>(); // stores x-y values 11 12 // Initialize both TreeMaps with all points 13 for (int[] point : points) { 14 int xCoord = point[0]; 15 int yCoord = point[1]; 16 17 // Add transformed coordinates to maps 18 sumCoordinates.merge(xCoord + yCoord, 1, Integer::sum); 19 diffCoordinates.merge(xCoord - yCoord, 1, Integer::sum); 20 } 21 22 int minimumMaxDistance = Integer.MAX_VALUE; 23 24 // Try removing each point and calculate the resulting maximum distance 25 for (int[] point : points) { 26 int xCoord = point[0]; 27 int yCoord = point[1]; 28 29 // Remove current point from both maps 30 int sumKey = xCoord + yCoord; 31 if (sumCoordinates.merge(sumKey, -1, Integer::sum) == 0) { 32 sumCoordinates.remove(sumKey); 33 } 34 35 int diffKey = xCoord - yCoord; 36 if (diffCoordinates.merge(diffKey, -1, Integer::sum) == 0) { 37 diffCoordinates.remove(diffKey); 38 } 39 40 // Calculate maximum distance with current point removed 41 // Maximum distance is the max of ranges in both transformed coordinate systems 42 int maxDistanceAfterRemoval = Math.max( 43 sumCoordinates.lastKey() - sumCoordinates.firstKey(), 44 diffCoordinates.lastKey() - diffCoordinates.firstKey() 45 ); 46 47 // Update minimum of all maximum distances 48 minimumMaxDistance = Math.min(minimumMaxDistance, maxDistanceAfterRemoval); 49 50 // Add the point back to both maps for next iteration 51 sumCoordinates.merge(sumKey, 1, Integer::sum); 52 diffCoordinates.merge(diffKey, 1, Integer::sum); 53 } 54 55 return minimumMaxDistance; 56 } 57} 58

1class Solution { 2public: 3 int minimumDistance(vector<vector<int>>& points) { 4 // Use multisets to maintain sorted sums and differences 5 // For Manhattan distance, we transform coordinates: 6 // dist = max(|x1-x2| + |y1-y2|) = max(|(x1+y1)-(x2+y2)|, |(x1-y1)-(x2-y2)|) 7 multiset<int> sumCoordinates; // Stores (x + y) for all points 8 multiset<int> diffCoordinates; // Stores (x - y) for all points 9 10 // Populate both multisets with transformed coordinates 11 for (const auto& point : points) { 12 int x = point[0]; 13 int y = point[1]; 14 sumCoordinates.insert(x + y); 15 diffCoordinates.insert(x - y); 16 } 17 18 int minMaxDistance = INT_MAX; 19 20 // Try removing each point and calculate the maximum distance 21 for (const auto& point : points) { 22 int x = point[0]; 23 int y = point[1]; 24 25 // Remove current point from both multisets 26 sumCoordinates.erase(sumCoordinates.find(x + y)); 27 diffCoordinates.erase(diffCoordinates.find(x - y)); 28 29 // Calculate maximum Manhattan distance without current point 30 // Maximum distance is the max of the two ranges 31 int maxSumRange = *sumCoordinates.rbegin() - *sumCoordinates.begin(); 32 int maxDiffRange = *diffCoordinates.rbegin() - *diffCoordinates.begin(); 33 int currentMaxDistance = max(maxSumRange, maxDiffRange); 34 35 // Update minimum of all maximum distances 36 minMaxDistance = min(minMaxDistance, currentMaxDistance); 37 38 // Add the point back for next iteration 39 sumCoordinates.insert(x + y); 40 diffCoordinates.insert(x - y); 41 } 42 43 return minMaxDistance; 44 } 45}; 46

1// Calculate the minimum possible maximum Manhattan distance after removing one point 2function minimumDistance(points: number[][]): number { 3 // Create two multisets to track x+y and x-y values (Manhattan distance components) 4 const sumSet = new TreapMultiSet<number>(); 5 const diffSet = new TreapMultiSet<number>(); 6 7 // Add all points to both sets 8 for (const [x, y] of points) { 9 sumSet.add(x + y); 10 diffSet.add(x - y); 11 } 12 13 let minMaxDistance = Infinity; 14 15 // Try removing each point and calculate the resulting maximum distance 16 for (const [x, y] of points) { 17 // Temporarily remove the current point 18 sumSet.delete(x + y); 19 diffSet.delete(x - y); 20 21 // Calculate max distance without this point 22 const maxSum = sumSet.last() - sumSet.first(); 23 const maxDiff = diffSet.last() - diffSet.first(); 24 minMaxDistance = Math.min(minMaxDistance, Math.max(maxSum, maxDiff)); 25 26 // Add the point back 27 sumSet.add(x + y); 28 diffSet.add(x - y); 29 } 30 31 return minMaxDistance; 32} 33 34// Type definitions for comparison functions 35type CompareFunction<T, R extends 'number' | 'boolean'> = ( 36 a: T, 37 b: T, 38) => R extends 'number' ? number : boolean; 39 40// Interface defining the public API of TreapMultiSet 41interface ITreapMultiSet<T> extends Iterable<T> { 42 add: (...value: T[]) => this; 43 has: (value: T) => boolean; 44 delete: (value: T) => void; 45 46 bisectLeft: (value: T) => number; 47 bisectRight: (value: T) => number; 48 49 indexOf: (value: T) => number; 50 lastIndexOf: (value: T) => number; 51 52 at: (index: number) => T | undefined; 53 first: () => T | undefined; 54 last: () => T | undefined; 55 56 lower: (value: T) => T | undefined; 57 higher: (value: T) => T | undefined; 58 floor: (value: T) => T | undefined; 59 ceil: (value: T) => T | undefined; 60 61 shift: () => T | undefined; 62 pop: (index?: number) => T | undefined; 63 64 count: (value: T) => number; 65 66 keys: () => IterableIterator<T>; 67 values: () => IterableIterator<T>; 68 rvalues: () => IterableIterator<T>; 69 entries: () => IterableIterator<[number, T]>; 70 71 readonly size: number; 72} 73 74// Node class for the Treap data structure 75class TreapNode<T = number> { 76 value: T; 77 count: number; // Number of duplicate values 78 size: number; // Total size of subtree 79 priority: number; // Random priority for heap property 80 left: TreapNode<T> | null; 81 right: TreapNode<T> | null; 82 83 constructor(value: T) { 84 this.value = value; 85 this.count = 1; 86 this.size = 1; 87 this.priority = Math.random(); 88 this.left = null; 89 this.right = null; 90 } 91 92 // Get size of a node (handles null) 93 static getSize(node: TreapNode<any> | null): number { 94 return node?.size ?? 0; 95 } 96 97 // Get priority of a node (handles null) 98 static getFac(node: TreapNode<any> | null): number { 99 return node?.priority ?? 0; 100 } 101 102 // Update size based on children 103 pushUp(): void { 104 let totalSize = this.count; 105 totalSize += TreapNode.getSize(this.left); 106 totalSize += TreapNode.getSize(this.right); 107 this.size = totalSize; 108 } 109 110 // Right rotation for maintaining heap property 111 rotateRight(): TreapNode<T> { 112 let currentNode: TreapNode<T> = this; 113 const leftChild = currentNode.left; 114 currentNode.left = leftChild?.right ?? null; 115 if (leftChild) { 116 leftChild.right = currentNode; 117 currentNode = leftChild; 118 } 119 currentNode.right?.pushUp(); 120 currentNode.pushUp(); 121 return currentNode; 122 } 123 124 // Left rotation for maintaining heap property 125 rotateLeft(): TreapNode<T> { 126 let currentNode: TreapNode<T> = this; 127 const rightChild = currentNode.right; 128 currentNode.right = rightChild?.left ?? null; 129 if (rightChild) { 130 rightChild.left = currentNode; 131 currentNode = rightChild; 132 } 133 currentNode.left?.pushUp(); 134 currentNode.pushUp(); 135 return currentNode; 136 } 137} 138 139// Treap-based multiset implementation for maintaining sorted collections with duplicates 140class TreapMultiSet<T = number> implements ITreapMultiSet<T> { 141 private readonly root: TreapNode<T>; 142 private readonly compareFn: CompareFunction<T, 'number'>; 143 private readonly leftBound: T; 144 private readonly rightBound: T; 145 146 constructor(compareFn?: CompareFunction<T, 'number'>); 147 constructor(compareFn: CompareFunction<T, 'number'>, leftBound: T, rightBound: T); 148 constructor( 149 compareFn: CompareFunction<T, any> = (a: any, b: any) => a - b, 150 leftBound: any = -Infinity, 151 rightBound: any = Infinity, 152 ) { 153 // Initialize root with sentinel nodes for boundaries 154 this.root = new TreapNode<T>(rightBound); 155 this.root.priority = Infinity; 156 this.root.left = new TreapNode<T>(leftBound); 157 this.root.left.priority = -Infinity; 158 this.root.pushUp(); 159 160 this.leftBound = leftBound; 161 this.rightBound = rightBound; 162 this.compareFn = compareFn; 163 } 164 165 // Get the number of elements (excluding sentinels) 166 get size(): number { 167 return this.root.size - 2; 168 } 169 170 // Get the height of the tree 171 get height(): number { 172 const getHeight = (node: TreapNode<T> | null): number => { 173 if (node == null) return 0; 174 return 1 + Math.max(getHeight(node.left), getHeight(node.right)); 175 }; 176 return getHeight(this.root); 177 } 178 179 /** 180 * Check if a value exists in the set 181 * @complexity O(log n) 182 */ 183 has(value: T): boolean { 184 const compare = this.compareFn; 185 const search = (node: TreapNode<T> | null, value: T): boolean => { 186 if (node == null) return false; 187 const cmp = compare(node.value, value); 188 if (cmp === 0) return true; 189 if (cmp < 0) return search(node.right, value); 190 return search(node.left, value); 191 }; 192 return search(this.root, value); 193 } 194 195 /** 196 * Add values to the sorted set 197 * @complexity O(log n) per value 198 */ 199 add(...values: T[]): this { 200 const compare = this.compareFn; 201 202 const insert = ( 203 node: TreapNode<T> | null, 204 value: T, 205 parent: TreapNode<T>, 206 direction: 'left' | 'right', 207 ): void => { 208 if (node == null) return; 209 210 const cmp = compare(node.value, value); 211 212 if (cmp === 0) { 213 // Value exists, increment count 214 node.count++; 215 node.pushUp(); 216 } else if (cmp > 0) { 217 // Go left 218 if (node.left) { 219 insert(node.left, value, node, 'left'); 220 } else { 221 node.left = new TreapNode(value); 222 node.pushUp(); 223 } 224 // Maintain heap property 225 if (TreapNode.getFac(node.left) > node.priority) { 226 parent[direction] = node.rotateRight(); 227 } 228 } else { 229 // Go right 230 if (node.right) { 231 insert(node.right, value, node, 'right'); 232 } else { 233 node.right = new TreapNode(value); 234 node.pushUp(); 235 } 236 // Maintain heap property 237 if (TreapNode.getFac(node.right) > node.priority) { 238 parent[direction] = node.rotateLeft(); 239 } 240 } 241 parent.pushUp(); 242 }; 243 244 values.forEach(value => insert(this.root.left, value, this.root, 'left')); 245 return this; 246 } 247 248 /** 249 * Remove a value from the set 250 * @complexity O(log n) 251 */ 252 delete(value: T): void { 253 const compare = this.compareFn; 254 255 const remove = ( 256 node: TreapNode<T> | null, 257 value: T, 258 parent: TreapNode<T>, 259 direction: 'left' | 'right', 260 ): void => { 261 if (node == null) return; 262 263 const cmp = compare(node.value, value); 264 265 if (cmp === 0) { 266 if (node.count > 1) { 267 // Multiple instances, just decrement 268 node.count--; 269 node?.pushUp(); 270 } else if (node.left == null && node.right == null) { 271 // Leaf node, remove it 272 parent[direction] = null; 273 } else { 274 // Internal node, rotate to leaf then remove 275 if (node.right == null || 276 TreapNode.getFac(node.left) > TreapNode.getFac(node.right)) { 277 parent[direction] = node.rotateRight(); 278 remove(parent[direction]?.right ?? null, value, parent[direction]!, 'right'); 279 } else { 280 parent[direction] = node.rotateLeft(); 281 remove(parent[direction]?.left ?? null, value, parent[direction]!, 'left'); 282 } 283 } 284 } else if (cmp > 0) { 285 remove(node.left, value, node, 'left'); 286 } else { 287 remove(node.right, value, node, 'right'); 288 } 289 290 parent?.pushUp(); 291 }; 292 293 remove(this.root.left, value, this.root, 'left'); 294 } 295 296 /** 297 * Find insertion point for value (before any existing equal values) 298 * @complexity O(log n) 299 */ 300 bisectLeft(value: T): number { 301 const compare = this.compareFn; 302 303 const search = (node: TreapNode<T> | null, value: T): number => { 304 if (node == null) return 0; 305 306 const cmp = compare(node.value, value); 307 if (cmp === 0) { 308 return TreapNode.getSize(node.left); 309 } else if (cmp > 0) { 310 return search(node.left, value); 311 } else { 312 return search(node.right, value) + TreapNode.getSize(node.left) + node.count; 313 } 314 }; 315 316 return search(this.root, value) - 1; 317 } 318 319 /** 320 * Find insertion point for value (after any existing equal values) 321 * @complexity O(log n) 322 */ 323 bisectRight(value: T): number { 324 const compare = this.compareFn; 325 326 const search = (node: TreapNode<T> | null, value: T): number => { 327 if (node == null) return 0; 328 329 const cmp = compare(node.value, value); 330 if (cmp === 0) { 331 return TreapNode.getSize(node.left) + node.count; 332 } else if (cmp > 0) { 333 return search(node.left, value); 334 } else { 335 return search(node.right, value) + TreapNode.getSize(node.left) + node.count; 336 } 337 }; 338 339 return search(this.root, value) - 1; 340 } 341 342 /** 343 * Find the first index of a value 344 * @complexity O(log n) 345 */ 346 indexOf(value: T): number { 347 const compare = this.compareFn; 348 let found = false; 349 350 const search = (node: TreapNode<T> | null, value: T): number => { 351 if (node == null) return 0; 352 353 const cmp = compare(node.value, value); 354 if (cmp === 0) { 355 found = true; 356 return TreapNode.getSize(node.left); 357 } else if (cmp > 0) { 358 return search(node.left, value); 359 } else { 360 return search(node.right, value) + TreapNode.getSize(node.left) + node.count; 361 } 362 }; 363 364 const result = search(this.root, value) - 1; 365 return found ? result : -1; 366 } 367 368 /** 369 * Find the last index of a value 370 * @complexity O(log n) 371 */ 372 lastIndexOf(value: T): number { 373 const compare = this.compareFn; 374 let found = false; 375 376 const search = (node: TreapNode<T> | null, value: T): number => { 377 if (node == null) return 0; 378 379 const cmp = compare(node.value, value); 380 if (cmp === 0) { 381 found = true; 382 return TreapNode.getSize(node.left) + node.count - 1; 383 } else if (cmp > 0) { 384 return search(node.left, value); 385 } else { 386 return search(node.right, value) + TreapNode.getSize(node.left) + node.count; 387 } 388 }; 389 390 const result = search(this.root, value) - 1; 391 return found ? result : -1; 392 } 393 394 /** 395 * Get element at specific index 396 * @complexity O(log n) 397 */ 398 at(index: number): T | undefined { 399 // Handle negative indices 400 if (index < 0) index += this.size; 401 if (index < 0 || index >= this.size) return undefined; 402 403 const findByRank = (node: TreapNode<T> | null, rank: number): T | undefined => { 404 if (node == null) return undefined; 405 406 const leftSize = TreapNode.getSize(node.left); 407 if (leftSize >= rank) { 408 return findByRank(node.left, rank); 409 } else if (leftSize + node.count >= rank) { 410 return node.value; 411 } else { 412 return findByRank(node.right, rank - leftSize - node.count); 413 } 414 }; 415 416 const result = findByRank(this.root, index + 2); 417 return ([this.leftBound, this.rightBound] as any[]).includes(result) ? undefined : result; 418 } 419 420 /** 421 * Find the largest element less than value 422 * @complexity O(log n) 423 */ 424 lower(value: T): T | undefined { 425 const compare = this.compareFn; 426 427 const search = (node: TreapNode<T> | null, value: T): T | undefined => { 428 if (node == null) return undefined; 429 430 if (compare(node.value, value) >= 0) { 431 return search(node.left, value); 432 } 433 434 const rightResult = search(node.right, value); 435 if (rightResult == null || compare(node.value, rightResult) > 0) { 436 return node.value; 437 } 438 return rightResult; 439 }; 440 441 const result = search(this.root, value) as any; 442 return result === this.leftBound ? undefined : result; 443 } 444 445 /** 446 * Find the smallest element greater than value 447 * @complexity O(log n) 448 */ 449 higher(value: T): T | undefined { 450 const compare = this.compareFn; 451 452 const search = (node: TreapNode<T> | null, value: T): T | undefined => { 453 if (node == null) return undefined; 454 455 if (compare(node.value, value) <= 0) { 456 return search(node.right, value); 457 } 458 459 const leftResult = search(node.left, value); 460 if (leftResult == null || compare(node.value, leftResult) < 0) { 461 return node.value; 462 } 463 return leftResult; 464 }; 465 466 const result = search(this.root, value) as any; 467 return result === this.rightBound ? undefined : result; 468 } 469 470 /** 471 * Find the largest element less than or equal to value 472 * @complexity O(log n) 473 */ 474 floor(value: T): T | undefined { 475 const compare = this.compareFn; 476 477 const search = (node: TreapNode<T> | null, value: T): T | undefined => { 478 if (node == null) return undefined; 479 480 const cmp = compare(node.value, value); 481 if (cmp === 0) return node.value; 482 if (cmp >= 0) return search(node.left, value); 483 484 const rightResult = search(node.right, value); 485 if (rightResult == null || compare(node.value, rightResult) > 0) { 486 return node.value; 487 } 488 return rightResult; 489 }; 490 491 const result = search(this.root, value) as any; 492 return result === this.leftBound ? undefined : result; 493 } 494 495 /** 496 * Find the smallest element greater than or equal to value 497 * @complexity O(log n) 498 */ 499 ceil(value: T): T | undefined { 500 const compare = this.compareFn; 501 502 const search = (node: TreapNode<T> | null, value: T): T | undefined => { 503 if (node == null) return undefined; 504 505 const cmp = compare(node.value, value); 506 if (cmp === 0) return node.value; 507 if (cmp <= 0) return search(node.right, value); 508 509 const leftResult = search(node.left, value); 510 if (leftResult == null || compare(node.value, leftResult) < 0) { 511 return node.value; 512 } 513 return leftResult; 514 }; 515 516 const result = search(this.root, value) as any; 517 return result === this.rightBound ? undefined : result; 518 } 519 520 /** 521 * Get the minimum element 522 * @complexity O(log n) 523 */ 524 first(): T | undefined { 525 const iterator = this.inOrder(); 526 iterator.next(); // Skip left bound 527 const result = iterator.next().value; 528 return result === this.rightBound ? undefined : result; 529 } 530 531 /** 532 * Get the maximum element 533 * @complexity O(log n) 534 */ 535 last(): T | undefined { 536 const iterator = this.reverseInOrder(); 537 iterator.next(); // Skip right bound 538 const result = iterator.next().value; 539 return result === this.leftBound ? undefined : result; 540 } 541 542 /** 543 * Remove and return the minimum element 544 * @complexity O(log n) 545 */ 546 shift(): T | undefined { 547 const firstElement = this.first(); 548 if (firstElement === undefined) return undefined; 549 this.delete(firstElement); 550 return firstElement; 551 } 552 553 /** 554 * Remove and return the maximum element or element at index 555 * @complexity O(log n) 556 */ 557 pop(index?: number): T | undefined { 558 if (index == null) { 559 const lastElement = this.last(); 560 if (lastElement === undefined) return undefined; 561 this.delete(lastElement); 562 return lastElement; 563 } 564 565 const elementToDelete = this.at(index); 566 if (elementToDelete == null) return; 567 this.delete(elementToDelete); 568 return elementToDelete; 569 } 570 571 /** 572 * Count occurrences of a value 573 * @complexity O(log n) 574 */ 575 count(value: T): number { 576 const compare = this.compareFn; 577 578 const search = (node: TreapNode<T> | null, value: T): number => { 579 if (node == null) return 0; 580 581 const cmp = compare(node.value, value); 582 if (cmp === 0) return node.count; 583 if (cmp < 0) return search(node.right, value); 584 return search(node.left, value); 585 }; 586 587 return search(this.root, value); 588 } 589 590 // Iterator implementation 591 *[Symbol.iterator](): Generator<T, any, any> { 592 yield* this.values(); 593 } 594 595 /** 596 * Get an iterator for all keys 597 */ 598 *keys(): Generator<T, any, any> { 599 yield* this.values(); 600 } 601 602 /** 603 * Get an iterator for all values in sorted order 604 */ 605 *values(): Generator<T, any, any> { 606 const iterator = this.inOrder(); 607 iterator.next(); // Skip left bound 608 const totalSteps = this.size; 609 for (let i = 0; i < totalSteps; i++) { 610 yield iterator.next().value; 611 } 612 } 613 614 /** 615 * Get an iterator for all values in reverse order 616 */ 617 *rvalues(): Generator<T, any, any> { 618 const iterator = this.reverseInOrder(); 619 iterator.next(); // Skip right bound 620 const totalSteps = this.size; 621 for (let i = 0; i < totalSteps; i++) { 622 yield iterator.next().value; 623 } 624 } 625 626 /** 627 * Get an iterator for [index, value] pairs 628 */ 629 *entries(): IterableIterator<[number, T]> { 630 const iterator = this.inOrder(); 631 iterator.next(); // Skip left bound 632 const totalSteps = this.size; 633 for (let i = 0; i < totalSteps; i++) { 634 yield [i, iterator.next().value]; 635 } 636 } 637 638 // In-order traversal generator 639 private *inOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> { 640 if (root == null) return; 641 642 yield* this.inOrder(root.left); 643 644 const duplicates = root.count; 645 for (let i = 0; i < duplicates; i++) { 646 yield root.value; 647 } 648 649 yield* this.inOrder(root.right); 650 } 651 652 // Reverse in-order traversal generator 653 private *reverseInOrder(root: TreapNode<T> | null = this.root): Generator<T, any, any> { 654 if (root == null) return; 655 656 yield* this.reverseInOrder(root.right); 657 658 const duplicates = root.count; 659 for (let i = 0; i < duplicates; i++) { 660 yield root.value; 661 } 662 663 yield* this.reverseInOrder(root.left); 664 } 665} 666

Solution Approach

Based on the mathematical transformation discussed, we implement the solution using ordered sets (SortedList in Python) to efficiently maintain and query the extreme values.

Step 1: Initialize Data Structures

We create two SortedLists:

sl1: stores x + y values for all points
sl2: stores x - y values for all points

sl1 = SortedList() sl2 = SortedList() for x, y in points:  sl1.add(x + y)  sl2.add(x - y)

Step 2: Try Removing Each Point

For each point in the array, we temporarily remove it and calculate the resulting maximum distance:

ans = inf for x, y in points:  # Remove current point from both sorted lists  sl1.remove(x + y)  sl2.remove(x - y)   # Calculate max distance without this point  # Maximum distance is the max of the two ranges  ans = min(ans, max(sl1[-1] - sl1[0], sl2[-1] - sl2[0]))   # Add the point back for next iteration  sl1.add(x + y)  sl2.add(x - y)

Key Operations:

sl1[-1] - sl1[0]: gives the range of x + y values (max minus min)
sl2[-1] - sl2[0]: gives the range of x - y values (max minus min)
The maximum of these two ranges determines the maximum Manhattan distance in the remaining points

Time Complexity Analysis:

Initial population of sorted lists: O(n log n)
For each of n points:
- Remove from sorted lists: O(log n)
- Calculate range: O(1)
- Add back to sorted lists: O(log n)
Total: O(n log n)

Space Complexity: O(n) for storing the two sorted lists

The algorithm efficiently finds the minimum possible maximum distance by leveraging the mathematical property that Manhattan distance can be expressed in terms of x + y and x - y, allowing us to avoid the brute force approach of calculating all pairwise distances.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through the solution with a small example to illustrate how the algorithm works.

Given points: [[1, 1], [3, 3], [5, 1]]

Step 1: Calculate transformed coordinates

For each point, we calculate x + y and x - y:

Point [1, 1]: x + y = 2, x - y = 0
Point [3, 3]: x + y = 6, x - y = 0
Point [5, 1]: x + y = 6, x - y = 4

Initialize sorted lists:

sl1 (x + y values): [2, 6, 6]
sl2 (x - y values): [0, 0, 4]

Step 2: Try removing each point

Remove Point [1, 1]:

Remove from sorted lists: sl1 = [6, 6], sl2 = [0, 4]
Calculate ranges:
- Range of x + y: 6 - 6 = 0
- Range of x - y: 4 - 0 = 4
- Max distance = max(0, 4) = 4
Add point back: sl1 = [2, 6, 6], sl2 = [0, 0, 4]

Remove Point [3, 3]:

Remove from sorted lists: sl1 = [2, 6], sl2 = [0, 4]
Calculate ranges:
- Range of x + y: 6 - 2 = 4
- Range of x - y: 4 - 0 = 4
- Max distance = max(4, 4) = 4
Add point back: sl1 = [2, 6, 6], sl2 = [0, 0, 4]

Remove Point [5, 1]:

Remove from sorted lists: sl1 = [2, 6], sl2 = [0, 0]
Calculate ranges:
- Range of x + y: 6 - 2 = 4
- Range of x - y: 0 - 0 = 0
- Max distance = max(4, 0) = 4
Add point back: sl1 = [2, 6, 6], sl2 = [0, 0, 4]

Step 3: Return minimum result

All removals resulted in a maximum distance of 4, so the answer is 4.

Verification: Let's verify by checking actual Manhattan distances:

Without [1, 1]: distance([3, 3], [5, 1]) = |3-5| + |3-1| = 2 + 2 = 4 ✓
Without [3, 3]: distance([1, 1], [5, 1]) = |1-5| + |1-1| = 4 + 0 = 4 ✓
Without [5, 1]: distance([1, 1], [3, 3]) = |1-3| + |1-3| = 2 + 2 = 4 ✓

The algorithm correctly identifies that removing any point results in the same maximum distance of 4.

Time and Space Complexity

The time complexity is O(n log n), where n is the number of points.

Time Complexity Analysis:

Initially, we add all n points to two SortedLists (sl1 and sl2). Each insertion into a SortedList takes O(log n) time, so this initialization phase takes O(n log n) time.
Then we iterate through all n points:
- For each point, we remove it from both SortedLists: O(log n) per removal, so O(log n) total
- We access the first and last elements of both SortedLists: O(1) time
- We add the point back to both SortedLists: O(log n) per addition, so O(log n) total
- Each iteration takes O(log n) time
The loop runs n times, giving us O(n log n) for the main loop
Overall time complexity: O(n log n) + O(n log n) = O(n log n)

The space complexity is O(n).

Space Complexity Analysis:

Two SortedLists (sl1 and sl2) each store n values (transformed coordinates x + y and x - y)
Each SortedList requires O(n) space
Total space used: O(n) + O(n) = O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Manhattan Distance Formula Implementation

A common mistake is trying to directly calculate Manhattan distance as max(|x1-x2|, |y1-y2|) instead of |x1-x2| + |y1-y2|. This confusion often arises from mixing up Manhattan distance with Chebyshev distance.

Wrong approach:

# Incorrect - this is Chebyshev distance, not Manhattan distance = max(abs(x1 - x2), abs(y1 - y2))

Correct approach:

# Correct Manhattan distance distance = abs(x1 - x2) + abs(y1 - y2) # Or using the transformation distance = max(abs((x1+y1) - (x2+y2)), abs((x1-y1) - (x2-y2)))

2. Edge Case: Array with Only 3 Points

When the array has exactly 3 points, after removing one point, only 2 points remain. The code might break if not handling empty ranges properly.

Problematic scenario:

# If points array has less than 3 points after removal if len(sum_sorted) < 2:  # sum_sorted[-1] - sum_sorted[0] would fail or give 0

Solution:

# Add a check before calculating distances if len(points) <= 2:  return 0 # No distance if only 1 point remains after removal  # Or handle in the main loop if len(sum_sorted) == 0:  max_distance = 0 else:  max_distance = max(sum_sorted[-1] - sum_sorted[0],  diff_sorted[-1] - diff_sorted[0])

3. Using Regular List Instead of SortedList

Attempting to use a regular Python list with manual sorting leads to inefficient O(n²log n) complexity due to repeated sorting operations.

Inefficient approach:

# Wrong - this requires O(n log n) sorting for each removal sum_list = [] for x, y in points:  sum_list.append(x + y) sum_list.sort() # O(n log n) each time  # For each point removal sum_list.remove(x + y) # O(n) to find and remove sum_list.sort() # Another O(n log n) - very inefficient!

Correct approach:

from sortedcontainers import SortedList # SortedList maintains order automatically sum_sorted = SortedList() # O(log n) for add/remove operations sum_sorted.add(x + y) sum_sorted.remove(x + y)

4. Forgetting to Add Points Back After Temporary Removal

A critical error is forgetting to add the point back after calculating the maximum distance without it. This would corrupt the data for subsequent iterations.

Bug-prone code:

for x, y in points:  sum_sorted.remove(x + y)  diff_sorted.remove(x - y)   max_distance = max(sum_sorted[-1] - sum_sorted[0],  diff_sorted[-1] - diff_sorted[0])  min_max_distance = min(min_max_distance, max_distance)   # Forgot to add back! Next iteration will have wrong data  # sum_sorted.add(x + y) # Missing!  # diff_sorted.add(x - y) # Missing!

5. Not Handling Duplicate Points Correctly

If the input contains duplicate points, removing one instance might accidentally affect calculations for another identical point.

Potential issue:

# If points = [[1,1], [1,1], [3,3]] # When removing first [1,1], we might accidentally affect the second [1,1]

Solution: The current implementation using SortedList.remove() only removes one instance, which is correct. However, be aware that if using sets or other data structures, duplicates need special handling.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers