3102. Minimize Manhattan Distances

Problem Description

You are given an array points representing integer coordinates of some points on a 2D plane, where points[i] = [x_i, y_i].

The distance between two points is defined as their Manhattan distance.

Return the minimum possible value for the maximum distance between any two points by removing exactly one point.

Intuition

The task is to minimize the maximum Manhattan distance between any two points after removing one point. The Manhattan distance between two points (x_1, y_1) and (x_2, y_2) can be expressed in different ways, but with some transformation, it can be simplified to:

max((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)).

This simplification highlights that the Manhattan distance can be broken into two components:

The maximum range of x + y
The maximum range of x - y

By storing the values of x + y and x - y for all points in two separate ordered sets, we can efficiently calculate the maximum and minimum values of these quantities. For each point, remove its contribution from the sets, calculate the new potential maximum distance when this point is omitted, and update the answer accordingly. Finally, return the smallest maximum distance obtained.

Learn more about Math and Sorting patterns.

Solution Approach

To solve the problem, we use an efficient approach leveraging the properties of the SortedList from the sortedcontainers module in Python. This data structure allows for logarithmic time complexity to insert and delete elements while maintaining order.

Here's a step-by-step breakdown of the solution:

Initialize Sorted Lists:
- Create two SortedList instances, sl1 and sl2, to keep track of the x + y and x - y values of each point, respectively.
Populate Sorted Lists:
- Iterate through each point (x, y) in the input list points.
- Compute x + y and x - y for each point and add these values to sl1 and sl2.
Compute Minimum Maximum Distance:
- Initialize a variable ans to store the result, starting with inf.
- For each point (x, y):
  - Remove the point's x + y and x - y values from sl1 and sl2.
  - Calculate the maximum range of x + y and x - y by taking the difference between the maximum and minimum elements in sl1 and sl2.
  - The current maximum Manhattan distance is given by the larger of these two ranges.
  - Update ans with the minimum of itself and the current maximum distance.
  - Add the removed values back to sl1 and sl2 to restore them for the next iteration.
Return the Result:
- After processing all points, ans will contain the smallest possible value of the maximum distance when one point is removed.

The key aspect of this solution is efficiently calculating and updating the potential maximum distances after removing each point, leveraging the properties of ordered sets provided by SortedList.

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        sl1 = SortedList()
        sl2 = SortedList()
        for x, y in points:
            sl1.add(x + y)
            sl2.add(x - y)
        ans = inf
        for x, y in points:
            sl1.remove(x + y)
            sl2.remove(x - y)
            ans = min(ans, max(sl1[-1] - sl1[0], sl2[-1] - sl2[0]))
            sl1.add(x + y)
            sl2.add(x - y)
        return ans

This algorithm efficiently exploits the mathematical transformation of the problem and the properties of SortedList to achieve the desired result efficiently.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's consider points = [[1, 2], [3, 4], [5, 6], [7, 8]] and apply the solution approach step-by-step:

Initialize Sorted Lists:
- Create two SortedList instances: sl1 for storing x + y values and sl2 for storing x - y values.

Populate Sorted Lists:

Compute x + y and x - y for each point and add them to sl1 and sl2.

Points:           [1, 2]   [3, 4]   [5, 6]   [7, 8]
x + y values:     3       7       11      15
x - y values:    -1      -1      -1      -1

sl1 contains [3, 7, 11, 15]
sl2 contains [-1, -1, -1, -1]

Compute Minimum Maximum Distance:
- Initialize ans with inf.
- Iterate over each point, calculate maximum Manhattan distances, and update ans:
Iteration 1: Remove point [1, 2]:
- Remove 3 from sl1 and -1 from sl2.
- sl1 now: [7, 11, 15]
- sl2 now: [-1, -1, -1]
- Calculate maximum distance:
  - max(sl1[-1] - sl1[0], sl2[-1] - sl2[0]) = max(15 - 7, 0) = 8
- Update ans = min(ans, 8) → ans = 8
- Add 3 and -1 back.
Iteration 2: Remove point [3, 4]:
- Remove 7 from sl1 and -1 from sl2.
- sl1 now: [3, 11, 15]
- sl2 now: [-1, -1, -1]
- Calculate maximum distance:
  - Max distance remains max(15 - 3, 0) = 12
- ans = min(ans, 12) → ans = 8
- Add 7 and -1 back.
Iteration 3: Remove point [5, 6]:
- Remove 11 from sl1 and -1 from sl2.
- sl1 now: [3, 7, 15]
- sl2 now: [-1, -1, -1]
- Calculate maximum distance:
  - Max distance remains max(15 - 3, 0) = 12
- ans = min(ans, 12) → ans = 8
- Add 11 and -1 back.
Iteration 4: Remove point [7, 8]:
- Remove 15 from sl1 and -1 from sl2.
- sl1 now: [3, 7, 11]
- sl2 now: [-1, -1, -1]
- Calculate maximum distance:
  - Max distance remains max(11 - 3, 0) = 8
- ans = min(ans, 8) → ans = 8
- Add 15 and -1 back.
Return the Result:

The smallest possible value of the maximum distance when one point is removed is 8.

Solution Implementation

1from typing import List
2from sortedcontainers import SortedList
3from math import inf
4
5class Solution:
6    def minimumDistance(self, points: List[List[int]]) -> int:
7        sl1 = SortedList()  # Initialize a sorted list for x + y
8        sl2 = SortedList()  # Initialize a sorted list for x - y
9
10        # Populate the sorted lists with x + y and x - y values from the points
11        for x, y in points:
12            sl1.add(x + y)
13            sl2.add(x - y)
14      
15        # Initialize answer with infinity
16        ans = inf
17      
18        # Iterate over each point to check minimum distance
19        for x, y in points:
20            # Remove current point's x + y and x - y to find max distance without it
21            sl1.remove(x + y)
22            sl2.remove(x - y)
23          
24            # Calculate the max distance between the extremities of the sorted lists
25            current_distance = max(sl1[-1] - sl1[0], sl2[-1] - sl2[0])
26            # Update answer with the minimum distance found
27            ans = min(ans, current_distance)
28          
29            # Re-add the current point's x + y and x - y for further iterations
30            sl1.add(x + y)
31            sl2.add(x - y)
32      
33        return ans
34

1import java.util.TreeMap;
2
3class Solution {
4    public int minimumDistance(int[][] points) {
5        // TreeMap to store the combined coordinates x+y and their count
6        TreeMap<Integer, Integer> sumMap = new TreeMap<>();
7        // TreeMap to store the difference coordinates x-y and their count
8        TreeMap<Integer, Integer> diffMap = new TreeMap<>();
9
10        // Populate the TreeMaps with the respective coordinate transformations
11        for (int[] point : points) {
12            int x = point[0];
13            int y = point[1];
14            // Increment the count for x+y in sumMap
15            sumMap.merge(x + y, 1, Integer::sum);
16            // Increment the count for x-y in diffMap
17            diffMap.merge(x - y, 1, Integer::sum);
18        }
19
20        // Initialize answer with max integer value
21        int ans = Integer.MAX_VALUE;
22
23        // Iterate over each point to calculate the potential minimum distance
24        for (int[] point : points) {
25            int x = point[0];
26            int y = point[1];
27          
28            // Decrement the count of x+y in sumMap, remove if count goes to zero
29            if (sumMap.merge(x + y, -1, Integer::sum) == 0) {
30                sumMap.remove(x + y);
31            }
32
33            // Decrement the count of x-y in diffMap, remove if count goes to zero
34            if (diffMap.merge(x - y, -1, Integer::sum) == 0) {
35                diffMap.remove(x - y);
36            }
37
38            // Calculate the minimum of the current ans or max difference between keys in TreeMaps
39            ans = Math.min(
40                ans, Math.max(sumMap.lastKey() - sumMap.firstKey(), diffMap.lastKey() - diffMap.firstKey())
41            );
42
43            // Restore the count of x+y in sumMap
44            sumMap.merge(x + y, 1, Integer::sum);
45            // Restore the count of x-y in diffMap
46            diffMap.merge(x - y, 1, Integer::sum);
47        }
48      
49        // Return the minimum distance found
50        return ans;
51    }
52}
53

1class Solution {
2public:
3    int minimumDistance(vector<vector<int>>& points) {
4        // Use two multiset containers to keep track of transformed points
5        std::multiset<int> set1;
6        std::multiset<int> set2;
7
8        // Transform each point and insert into the multisets
9        for (auto& point : points) {
10            int x = point[0], y = point[1];
11            set1.insert(x + y);  // Store the sum of x and y
12            set2.insert(x - y);  // Store the difference of x and y
13        }
14
15        // Initialize the minimum answer with a large value
16        int answer = INT_MAX;
17
18        // Iterate over each point
19        for (auto& point : points) {
20            int x = point[0], y = point[1];
21          
22            // Remove the current transformed values from the multisets
23            set1.erase(set1.find(x + y));
24            set2.erase(set2.find(x - y));
25
26            // Calculate the new potential minimum distance
27            int maxDiff = std::max(*set1.rbegin() - *set1.begin(), *set2.rbegin() - *set2.begin());
28            answer = std::min(answer, maxDiff);
29
30            // Restore the transformed values back to the multisets
31            set1.insert(x + y);
32            set2.insert(x - y);
33        }
34
35        // Return the minimum possible distance found
36        return answer;
37    }
38};
39

1// Type used for values and results in comparison functions
2type CompareFunction<T, R extends 'number' | 'boolean'> = (a: T, b: T) => R extends 'number' ? number : boolean;
3
4// Node structure for Treap
5interface TreapNode<T> {
6    value: T;           // Value stored in the node
7    count: number;      // Count of duplicates
8    size: number;       // Size of the subtree rooted at this node
9    priority: number;   // Priority for balancing treap
10    left: TreapNode<T> | null;  // Left child
11    right: TreapNode<T> | null; // Right child
12}
13
14// Initialize a new node
15function createTreapNode<T>(value: T): TreapNode<T> {
16    return {
17        value,
18        count: 1,
19        size: 1,
20        priority: Math.random(),
21        left: null,
22        right: null
23    };
24}
25
26// Update size property of the node
27function pushUp(node: TreapNode<any>): void {
28    node.size = node.count + getSize(node.left) + getSize(node.right);
29}
30
31// Rotate the subtree right
32function rotateRight<T>(node: TreapNode<T>): TreapNode<T> {
33    const left = node.left!;
34    node.left = left.right;
35    left.right = node;
36    pushUp(node);
37    pushUp(left);
38    return left;
39}
40
41// Rotate the subtree left
42function rotateLeft<T>(node: TreapNode<T>): TreapNode<T> {
43    const right = node.right!;
44    node.right = right.left;
45    right.left = node;
46    pushUp(node);
47    pushUp(right);
48    return right;
49}
50
51// Get size of the node
52function getSize(node: TreapNode<any> | null): number {
53    return node ? node.size : 0;
54}
55
56// Get priority factor of the node
57function getFac(node: TreapNode<any> | null): number {
58    return node ? node.priority : 0;
59}
60
61// TreapMultiSet global variables
62let root: TreapNode<number> = createTreapNode(Infinity);
63let compareFn: CompareFunction<number, 'number'> = (a, b) => a - b;
64let leftBound: number = -Infinity;
65let rightBound: number = Infinity;
66
67// Initialize for new treap
68function initTreap(compareFnInit?: CompareFunction<number, 'number'>, leftBoundInit?: number, rightBoundInit?: number): void {
69    compareFn = compareFnInit || ((a, b) => a - b);
70    leftBound = leftBoundInit !== undefined ? leftBoundInit : -Infinity;
71    rightBound = rightBoundInit !== undefined ? rightBoundInit : Infinity;
72    root = createTreapNode(rightBound);
73    root.priority = Infinity;
74    root.left = createTreapNode(leftBound);
75    root.left.priority = -Infinity;
76    pushUp(root);
77}
78
79// Add values to the treap
80function add(...values: number[]): void {
81    for (const value of values) {
82        root.left = addNode(root.left, value, root, 'left');
83    }
84}
85
86// Helper function to recursively add a node
87function addNode(node: TreapNode<number> | null, value: number, parent: TreapNode<number>, direction: 'left' | 'right'): TreapNode<number> | null {
88    if (node === null) {
89        node = createTreapNode(value);
90    } else if (compareFn(node.value, value) === 0) {
91        node.count++;
92    } else if (compareFn(node.value, value) > 0) {
93        node.left = addNode(node.left, value, node, 'left');
94        if (getFac(node.left) > node.priority) {
95            return rotateRight(node);
96        }
97    } else {
98        node.right = addNode(node.right, value, node, 'right');
99        if (getFac(node.right) > node.priority) {
100            return rotateLeft(node);
101        }
102    }
103    pushUp(node);
104    return node;
105}
106
107// Remove value from the treap
108function deleteValue(value: number): void {
109    root.left = deleteNode(root.left, value, root, 'left');
110}
111
112// Helper function to recursively remove a node
113function deleteNode(node: TreapNode<number> | null, value: number, parent: TreapNode<number>, direction: 'left' | 'right'): TreapNode<number> | null {
114    if (node === null) return null;
115
116    if (compareFn(node.value, value) === 0) {
117        if (node.count > 1) {
118            node.count--;
119        } else if (node.left == null || node.right == null) {
120            return node.left ?? node.right;
121        } else if (getFac(node.left) > getFac(node.right)) {
122            parent[direction] = rotateRight(node);
123            return deleteNode(parent[direction]?.right, value, parent[direction]!, 'right');
124        } else {
125            parent[direction] = rotateLeft(node);
126            return deleteNode(parent[direction]?.left, value, parent[direction]!, 'left');
127        }
128    } else if (compareFn(node.value, value) > 0) {
129        node.left = deleteNode(node.left, value, node, 'left');
130    } else {
131        node.right = deleteNode(node.right, value, node, 'right');
132    }
133    pushUp(node);
134    return node;
135}
136
137// Find and return the smallest value in the treap
138function first(): number | undefined {
139    let node = root;
140    while (node.left && node.left.value !== leftBound) {
141        node = node.left;
142    }
143    return node.left ? node.left.value : undefined;
144}
145
146// Find and return the largest value in the treap
147function last(): number | undefined {
148    let node = root;
149    while (node.right && node.right.value !== rightBound) {
150        node = node.right;
151    }
152    return node.value !== rightBound ? node.value : undefined;
153}
154
155// Calculate the minimum distance based on input points
156function minimumDistance(points: number[][]): number {
157    initTreap();
158    const st1 = new TreapMultiSet<number>();
159    const st2 = new TreapMultiSet<number>();
160    for (const [x, y] of points) {
161        add(x + y);
162        add(x - y);
163    }
164    let ans = Infinity;
165    for (const [x, y] of points) {
166        deleteValue(x + y);
167        deleteValue(x - y);
168        ans = Math.min(ans, Math.max(last()! - first()!, last()! - first()!));
169        add(x + y);
170        add(x - y);
171    }
172    return ans;
173}
174

Time and Space Complexity

The time complexity of the code is O(n \log n) because the operations that dominate this complexity are the insertions and deletions from the SortedList, both of which take O(\log n) time. The loops iterate over all points and each loop iteration involves a fixed number of SortedList operations.

The space complexity of the code is O(n), where n is the number of points, since the two SortedList instances sl1 and sl2 store n elements each.

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

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

Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don’t know