Facebook Pixel

3102. Minimize Manhattan Distances

HardGeometryArrayMathOrdered SetSorting
Leetcode Link

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:

  1. You must remove exactly one point from the given set of points
  2. After removal, calculate all pairwise Manhattan distances between the remaining points
  3. Find the maximum distance among all these pairs
  4. 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:

  1. Remove a point from both lists
  2. Check the new maximum distance (which is the max of the two ranges)
  3. Add the point back
  4. 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 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.

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

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 two pointer techniques do you use to check if a string is a palindrome?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Sorting Summary

Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More