Facebook Pixel

2613. Beautiful Pairs 🔒

HardGeometryArrayMathDivide and ConquerOrdered SetSorting
Leetcode Link

Problem Description

You are given two 0-indexed integer arrays nums1 and nums2 of the same length. Your task is to find a beautiful pair of indices.

A pair of indices (i, j) where i < j is called beautiful if the value |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| is the smallest among all possible index pairs.

The expression |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| represents the Manhattan distance between two points (nums1[i], nums2[i]) and (nums1[j], nums2[j]) in a 2D plane.

You need to return the beautiful pair. If there are multiple beautiful pairs with the same minimum distance, return the lexicographically smallest pair.

Lexicographic ordering rules:

  • A pair (i₁, j₁) is lexicographically smaller than (i₂, j₂) if:
    • i₁ < i₂, or
    • i₁ == i₂ and j₁ < j₂

Note: |x| denotes the absolute value of x.

Example interpretation: If we treat each index k as a point with coordinates (nums1[k], nums2[k]), the problem asks us to find two distinct points (with indices i < j) that have the minimum Manhattan distance between them. The Manhattan distance between two points is the sum of the absolute differences of their coordinates.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The problem essentially asks us to find the closest pair of points in a 2D plane using Manhattan distance. Each index i corresponds to a point (nums1[i], nums2[i]).

The naive approach would be to check all possible pairs, which takes O(n²) time. However, we can optimize this using a divide-and-conquer strategy similar to the classic "closest pair of points" problem.

First, we need to handle a special case: duplicate points. If two indices map to the same point coordinates, their Manhattan distance is 0, which is the minimum possible. We can quickly identify this by grouping points by their coordinates and checking if any group has more than one index.

For the general case without duplicates, we can use divide and conquer with a clever optimization:

  1. Sort points by x-coordinate: This allows us to divide the problem space efficiently.

  2. Divide: Split the sorted points into left and right halves recursively, finding the minimum distance in each half.

  3. Conquer: The key insight is that after finding minimum distances d1 and d2 in the left and right halves, we only need to check points near the dividing line. Specifically, we only need to consider points whose x-distance from the middle line is at most min(d1, d2).

  4. Strip optimization: For points in this "strip" region around the middle, we sort them by y-coordinate. Then, for each point, we only need to check subsequent points until their y-difference exceeds the current minimum distance. This is because if |y2 - y1| > d, then the Manhattan distance |x2 - x1| + |y2 - y1| must be greater than d.

This divide-and-conquer approach with the strip optimization reduces the time complexity from O(n²) to O(n log n), making it efficient even for large inputs.

The lexicographic ordering requirement is handled by maintaining index pairs alongside distances and comparing them when distances are equal.

Learn more about Math, Divide and Conquer and Sorting patterns.

Solution Approach

The implementation follows the divide-and-conquer strategy with several key components:

1. Handle Duplicate Points

First, we use a dictionary pl to group points by their coordinates (x, y). If any coordinate pair has multiple indices, we immediately return the first two indices as they have Manhattan distance 0:

pl = defaultdict(list)
for i, (x, y) in enumerate(zip(nums1, nums2)):
    pl[(x, y)].append(i)
  
for i, (x, y) in enumerate(zip(nums1, nums2)):
    if len(pl[(x, y)]) > 1:
        return [i, pl[(x, y)][1]]

2. Prepare and Sort Points

Create a list of points where each point is a tuple (x, y, index). Sort this list by x-coordinate:

points = []
for i, (x, y) in enumerate(zip(nums1, nums2)):
    points.append((x, y, i))
points.sort()

3. Divide and Conquer Function (dfs)

The recursive function processes intervals [l, r]:

Base case: If l >= r, return infinity distance (no valid pair exists).

Divide step:

  • Calculate midpoint m = (l + r) >> 1
  • Recursively solve left half [l, m] getting (d1, pi1, pj1)
  • Recursively solve right half [m+1, r] getting (d2, pi2, pj2)
  • Choose the better result based on distance and lexicographic order

4. Merge and Strip Processing

After getting results from both halves, check pairs that cross the middle line:

x = points[m][0]  # x-coordinate of middle point
t = [p for p in points[l : r + 1] if abs(p[0] - x) <= d1]

This creates a "strip" of points within distance d1 from the middle x-coordinate.

Sort the strip by y-coordinate:

t.sort(key=lambda x: x[1])

5. Efficient Strip Checking

For each point in the strip, only check subsequent points while their y-difference is within the current minimum distance:

for i in range(len(t)):
    for j in range(i + 1, len(t)):
        if t[j][1] - t[i][1] > d1:
            break  # No need to check further
        pi, pj = sorted([t[i][2], t[j][2]])
        d = dist(t[i][0], t[i][1], t[j][0], t[j][1])
        if d < d1 or (d == d1 and (pi < pi1 or (pi == pi1 and pj < pj1))):
            d1, pi1, pj1 = d, pi, pj

6. Distance Calculation

The Manhattan distance is computed using:

def dist(x1: int, y1: int, x2: int, y2: int) -> int:
    return abs(x1 - x2) + abs(y1 - y2)

7. Final Result

The main function initiates the divide-and-conquer process on the entire sorted array and returns the indices of the beautiful pair:

_, pi, pj = dfs(0, len(points) - 1)
return [pi, pj]

The algorithm efficiently finds the closest pair of points with O(n log n) time complexity through sorting and divide-and-conquer, while the space complexity is O(n) for storing the points and intermediate results.

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 a small example to illustrate the solution approach.

Input: nums1 = [1, 5, 3], nums2 = [2, 3, 1]

This gives us three points in 2D space:

  • Index 0: Point (1, 2)
  • Index 1: Point (5, 3)
  • Index 2: Point (3, 1)

Step 1: Check for Duplicate Points We create a dictionary to group points by coordinates:

  • (1, 2) → [0]
  • (5, 3) → [1]
  • (3, 1) → [2]

No duplicates found, so we continue.

Step 2: Sort Points by X-coordinate After sorting by x-coordinate:

  • Point (1, 2) with index 0
  • Point (3, 1) with index 2
  • Point (5, 3) with index 1

Our sorted array: [(1, 2, 0), (3, 1, 2), (5, 3, 1)]

Step 3: Divide and Conquer

Initial call: dfs(0, 2) (processing all 3 points)

  1. First Division:

    • Middle index m = 1
    • Left half: dfs(0, 1) processes points (1,2) and (3,1)
    • Right half: dfs(2, 2) returns infinity (single point)

  2. Processing Left Half dfs(0, 1):

    • Middle index m = 0
    • Left: dfs(0, 0) returns infinity
    • Right: dfs(1, 1) returns infinity
    • Check strip around x = 1:
      • Both points (1,2) and (3,1) are in strip
      • Distance = |1-3| + |2-1| = 2 + 1 = 3
      • Return (3, 0, 2)

  3. Back to Main Call:

    • Left result: (3, 0, 2) with distance 3
    • Right result: infinity
    • Current best: distance 3, pair (0, 2)

  4. Check Strip Around Middle (x = 3):

    • Points within distance 3 of x = 3: all three points
    • Sort by y-coordinate: [(3,1,2), (1,2,0), (5,3,1)]
    • Check pairs:
      • (3,1) and (1,2): distance = 2 + 1 = 3, indices (0,2) - same as current
      • (3,1) and (5,3): distance = 2 + 2 = 4, indices (1,2) - worse
      • (1,2) and (5,3): distance = 4 + 1 = 5, indices (0,1) - worse

Step 4: Final Result The beautiful pair is (0, 2) with Manhattan distance 3.

Verification:

  • Pair (0,1): |1-5| + |2-3| = 4 + 1 = 5
  • Pair (0,2): |1-3| + |2-1| = 2 + 1 = 3 ✓ (minimum)
  • Pair (1,2): |5-3| + |3-1| = 2 + 2 = 4

The algorithm correctly identifies (0,2) as the beautiful pair with the minimum Manhattan distance of 3.

Solution Implementation

1class Solution:
2    def beautifulPair(self, nums1: List[int], nums2: List[int]) -> List[int]:
3        def calculate_manhattan_distance(x1: int, y1: int, x2: int, y2: int) -> int:
4            """Calculate Manhattan distance between two points."""
5            return abs(x1 - x2) + abs(y1 - y2)
6
7        def divide_and_conquer(left: int, right: int) -> tuple[int, int, int]:
8            """
9            Find the closest pair of points using divide and conquer.
10            Returns: (minimum_distance, index_i, index_j)
11            """
12            # Base case: no valid pair in this range
13            if left >= right:
14                return float('inf'), -1, -1
15          
16            # Divide: split the range at midpoint
17            mid = (left + right) >> 1
18            mid_x = points[mid][0]
19          
20            # Conquer: recursively find closest pairs in left and right halves
21            dist_left, idx_i_left, idx_j_left = divide_and_conquer(left, mid)
22            dist_right, idx_i_right, idx_j_right = divide_and_conquer(mid + 1, right)
23          
24            # Choose the better result (smaller distance, or lexicographically smaller indices)
25            if dist_left > dist_right or (dist_left == dist_right and 
26                (idx_i_left > idx_i_right or (idx_i_left == idx_i_right and idx_j_left > idx_j_right))):
27                dist_left, idx_i_left, idx_j_left = dist_right, idx_i_right, idx_j_right
28          
29            # Combine: check points near the dividing line
30            # Only consider points within distance dist_left from the dividing line
31            strip_points = [p for p in points[left:right + 1] if abs(p[0] - mid_x) <= dist_left]
32            strip_points.sort(key=lambda point: point[1])  # Sort by y-coordinate
33          
34            # Check pairs in the strip
35            for i in range(len(strip_points)):
36                for j in range(i + 1, len(strip_points)):
37                    # If y-distance exceeds current minimum, no need to check further
38                    if strip_points[j][1] - strip_points[i][1] > dist_left:
39                        break
40                  
41                    # Get original indices in sorted order
42                    idx_i, idx_j = sorted([strip_points[i][2], strip_points[j][2]])
43                    current_dist = calculate_manhattan_distance(
44                        strip_points[i][0], strip_points[i][1], 
45                        strip_points[j][0], strip_points[j][1]
46                    )
47                  
48                    # Update if we found a better pair
49                    if current_dist < dist_left or (current_dist == dist_left and 
50                        (idx_i < idx_i_left or (idx_i == idx_i_left and idx_j < idx_j_left))):
51                        dist_left, idx_i_left, idx_j_left = current_dist, idx_i, idx_j
52          
53            return dist_left, idx_i_left, idx_j_left
54
55        # Create a map to track duplicate points
56        point_indices = defaultdict(list)
57        for i, (x, y) in enumerate(zip(nums1, nums2)):
58            point_indices[(x, y)].append(i)
59      
60        # Check for duplicate points (distance = 0)
61        points = []
62        for i, (x, y) in enumerate(zip(nums1, nums2)):
63            if len(point_indices[(x, y)]) > 1:
64                # Found duplicate points, return the first two indices
65                return [i, point_indices[(x, y)][1]]
66            points.append((x, y, i))  # Store (x, y, original_index)
67      
68        # Sort points by x-coordinate for divide and conquer
69        points.sort()
70      
71        # Find the closest pair using divide and conquer
72        _, index_i, index_j = divide_and_conquer(0, len(points) - 1)
73        return [index_i, index_j]
74
1class Solution {
2    // List to store points with their coordinates and indices
3    private List<int[]> points = new ArrayList<>();
4
5    /**
6     * Finds a beautiful pair of indices where the Manhattan distance is minimized.
7     * If multiple pairs have the same distance, returns the lexicographically smallest pair.
8     * 
9     * @param nums1 Array of x-coordinates
10     * @param nums2 Array of y-coordinates
11     * @return Array containing two indices [i, j] where i < j
12     */
13    public int[] beautifulPair(int[] nums1, int[] nums2) {
14        int n = nums1.length;
15      
16        // Map to group points by their encoded coordinates
17        Map<Long, List<Integer>> pointsByCoordinate = new HashMap<>();
18      
19        // Group indices by their coordinate values
20        for (int i = 0; i < n; ++i) {
21            long encodedCoordinate = encodeCoordinates(nums1[i], nums2[i]);
22            pointsByCoordinate.computeIfAbsent(encodedCoordinate, k -> new ArrayList<>()).add(i);
23        }
24      
25        // Check if any two points share the same coordinates (distance = 0)
26        for (int i = 0; i < n; ++i) {
27            long encodedCoordinate = encodeCoordinates(nums1[i], nums2[i]);
28            if (pointsByCoordinate.get(encodedCoordinate).size() > 1) {
29                // Return the first two indices with same coordinates
30                return new int[] {i, pointsByCoordinate.get(encodedCoordinate).get(1)};
31            }
32            // Store point information: [x-coordinate, y-coordinate, original index]
33            points.add(new int[] {nums1[i], nums2[i], i});
34        }
35      
36        // Sort points by x-coordinate for divide and conquer approach
37        points.sort((a, b) -> a[0] - b[0]);
38      
39        // Find closest pair using divide and conquer
40        int[] result = findClosestPair(0, points.size() - 1);
41      
42        // Return the pair of indices
43        return new int[] {result[1], result[2]};
44    }
45
46    /**
47     * Encodes x and y coordinates into a single long value for hashing.
48     * 
49     * @param x X-coordinate
50     * @param y Y-coordinate
51     * @return Encoded coordinate value
52     */
53    private long encodeCoordinates(int x, int y) {
54        return x * 100000L + y;
55    }
56
57    /**
58     * Calculates Manhattan distance between two points.
59     * 
60     * @param x1 X-coordinate of first point
61     * @param y1 Y-coordinate of first point
62     * @param x2 X-coordinate of second point
63     * @param y2 Y-coordinate of second point
64     * @return Manhattan distance
65     */
66    private int calculateManhattanDistance(int x1, int y1, int x2, int y2) {
67        return Math.abs(x1 - x2) + Math.abs(y1 - y2);
68    }
69
70    /**
71     * Recursively finds the closest pair of points using divide and conquer.
72     * 
73     * @param left Left boundary index
74     * @param right Right boundary index
75     * @return Array containing [minimum distance, first index, second index]
76     */
77    private int[] findClosestPair(int left, int right) {
78        // Base case: no valid pair exists
79        if (left >= right) {
80            return new int[] {1 << 30, -1, -1}; // Return large distance as sentinel
81        }
82      
83        // Find middle point
84        int mid = (left + right) >> 1;
85        int midX = points.get(mid)[0];
86      
87        // Recursively find closest pairs in left and right halves
88        int[] leftResult = findClosestPair(left, mid);
89        int[] rightResult = findClosestPair(mid + 1, right);
90      
91        // Choose the better result (smaller distance or lexicographically smaller indices)
92        if (rightResult[0] < leftResult[0] || 
93            (rightResult[0] == leftResult[0] && 
94             (rightResult[1] < leftResult[1] || 
95              (rightResult[1] == leftResult[1] && rightResult[2] < leftResult[2])))) {
96            leftResult = rightResult;
97        }
98      
99        // Find points within the strip (x-distance <= current minimum distance)
100        List<int[]> strip = new ArrayList<>();
101        for (int i = left; i <= right; ++i) {
102            if (Math.abs(points.get(i)[0] - midX) <= leftResult[0]) {
103                strip.add(points.get(i));
104            }
105        }
106      
107        // Sort strip points by y-coordinate
108        strip.sort((a, b) -> a[1] - b[1]);
109      
110        // Check pairs within the strip
111        for (int i = 0; i < strip.size(); ++i) {
112            for (int j = i + 1; j < strip.size(); ++j) {
113                // If y-distance exceeds current minimum, no need to check further
114                if (strip.get(j)[1] - strip.get(i)[1] > leftResult[0]) {
115                    break;
116                }
117              
118                // Ensure indices are in ascending order
119                int firstIndex = Math.min(strip.get(i)[2], strip.get(j)[2]);
120                int secondIndex = Math.max(strip.get(i)[2], strip.get(j)[2]);
121              
122                // Calculate distance between current pair
123                int distance = calculateManhattanDistance(
124                    strip.get(i)[0], strip.get(i)[1], 
125                    strip.get(j)[0], strip.get(j)[1]
126                );
127              
128                // Update result if this pair is better
129                if (distance < leftResult[0] || 
130                    (distance == leftResult[0] && 
131                     (firstIndex < leftResult[1] || 
132                      (firstIndex == leftResult[1] && secondIndex < leftResult[2])))) {
133                    leftResult = new int[] {distance, firstIndex, secondIndex};
134                }
135            }
136        }
137      
138        return leftResult;
139    }
140}
141
1class Solution {
2public:
3    vector<int> beautifulPair(vector<int>& nums1, vector<int>& nums2) {
4        int n = nums1.size();
5      
6        // Map to store indices of points with the same coordinates
7        // Key: encoded coordinate value, Value: list of indices
8        unordered_map<long long, vector<int>> coordinateToIndices;
9        for (int i = 0; i < n; ++i) {
10            coordinateToIndices[encodeCoordinate(nums1[i], nums2[i])].push_back(i);
11        }
12      
13        // Check if there are duplicate points (distance = 0)
14        // If found, return the first two indices with same coordinates
15        vector<tuple<int, int, int>> points; // (x, y, index)
16        for (int i = 0; i < n; ++i) {
17            long long encodedValue = encodeCoordinate(nums1[i], nums2[i]);
18            if (coordinateToIndices[encodedValue].size() > 1) {
19                return {i, coordinateToIndices[encodedValue][1]};
20            }
21            points.emplace_back(nums1[i], nums2[i], i);
22        }
23
24        // Divide and conquer function to find closest pair of points
25        // Returns tuple of (minimum distance, index1, index2)
26        function<tuple<int, int, int>(int, int)> findClosestPair = [&](int left, int right) -> tuple<int, int, int> {
27            // Base case: invalid range
28            if (left >= right) {
29                return {1 << 30, -1, -1}; // Return large distance as sentinel value
30            }
31          
32            // Divide: find middle point
33            int mid = (left + right) >> 1;
34            int midX = get<0>(points[mid]);
35          
36            // Conquer: recursively find closest pairs in left and right halves
37            auto leftResult = findClosestPair(left, mid);
38            auto rightResult = findClosestPair(mid + 1, right);
39          
40            // Choose the better result (smaller distance, or smaller indices if distances are equal)
41            if (get<0>(leftResult) > get<0>(rightResult) || 
42                (get<0>(leftResult) == get<0>(rightResult) && 
43                 (get<1>(leftResult) > get<1>(rightResult) || 
44                  (get<1>(leftResult) == get<1>(rightResult) && get<2>(leftResult) > get<2>(rightResult))))) {
45                swap(leftResult, rightResult);
46            }
47          
48            // Combine: check points near the dividing line
49            vector<tuple<int, int, int>> stripPoints;
50            for (int i = left; i <= right; ++i) {
51                // Only consider points within minimum distance from dividing line
52                if (abs(get<0>(points[i]) - midX) <= get<0>(leftResult)) {
53                    stripPoints.emplace_back(points[i]);
54                }
55            }
56          
57            // Sort strip points by y-coordinate
58            sort(stripPoints.begin(), stripPoints.end(), [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) {
59                return get<1>(a) < get<1>(b);
60            });
61          
62            // Check pairs in the strip
63            for (int i = 0; i < stripPoints.size(); ++i) {
64                for (int j = i + 1; j < stripPoints.size(); ++j) {
65                    // If y-distance exceeds current minimum, no need to check further
66                    if (get<1>(stripPoints[j]) - get<1>(stripPoints[i]) > get<0>(leftResult)) {
67                        break;
68                    }
69                  
70                    // Ensure indices are in ascending order
71                    int smallerIndex = min(get<2>(stripPoints[i]), get<2>(stripPoints[j]));
72                    int largerIndex = max(get<2>(stripPoints[i]), get<2>(stripPoints[j]));
73                  
74                    // Calculate Manhattan distance
75                    int distance = calculateManhattanDistance(
76                        get<0>(stripPoints[i]), get<1>(stripPoints[i]),
77                        get<0>(stripPoints[j]), get<1>(stripPoints[j])
78                    );
79                  
80                    // Update result if this pair is better
81                    if (distance < get<0>(leftResult) || 
82                        (distance == get<0>(leftResult) && 
83                         (smallerIndex < get<1>(leftResult) || 
84                          (smallerIndex == get<1>(leftResult) && largerIndex < get<2>(leftResult))))) {
85                        leftResult = {distance, smallerIndex, largerIndex};
86                    }
87                }
88            }
89          
90            return leftResult;
91        };
92
93        // Sort points by x-coordinate for divide and conquer
94        sort(points.begin(), points.end());
95      
96        // Find the closest pair and return their indices
97        auto [minDistance, index1, index2] = findClosestPair(0, points.size() - 1);
98        return {index1, index2};
99    }
100
101private:
102    // Encode 2D coordinates into a single long long value
103    long long encodeCoordinate(int x, int y) {
104        return x * 100000LL + y;
105    }
106
107    // Calculate Manhattan distance between two points
108    int calculateManhattanDistance(int x1, int y1, int x2, int y2) {
109        return abs(x1 - x2) + abs(y1 - y2);
110    }
111};
112
1/**
2 * Finds a pair of indices representing the closest points between two arrays
3 * @param nums1 - First array of numbers representing x-coordinates
4 * @param nums2 - Second array of numbers representing y-coordinates
5 * @returns Array containing two indices of the closest pair
6 */
7function beautifulPair(nums1: number[], nums2: number[]): number[] {
8    // Map to store indices grouped by their combined hash value
9    const pointIndicesByHash: Map<number, number[]> = new Map();
10    const arrayLength = nums1.length;
11  
12    // Group indices by their point hash values
13    for (let i = 0; i < arrayLength; ++i) {
14        const hashValue = f(nums1[i], nums2[i]);
15        if (!pointIndicesByHash.has(hashValue)) {
16            pointIndicesByHash.set(hashValue, []);
17        }
18        pointIndicesByHash.get(hashValue)!.push(i);
19    }
20  
21    // Check if any points are duplicates (same coordinates)
22    const pointsWithIndices: number[][] = [];
23    for (let i = 0; i < arrayLength; ++i) {
24        const hashValue = f(nums1[i], nums2[i]);
25        // If duplicate points exist, return the first two indices
26        if (pointIndicesByHash.get(hashValue)!.length > 1) {
27            return [i, pointIndicesByHash.get(hashValue)![1]];
28        }
29        // Store point coordinates with index: [x, y, index]
30        pointsWithIndices.push([nums1[i], nums2[i], i]);
31    }
32  
33    // Sort points by x-coordinate for divide and conquer approach
34    pointsWithIndices.sort((a, b) => a[0] - b[0]);
35
36    /**
37     * Recursive divide and conquer function to find closest pair
38     * @param left - Left boundary index
39     * @param right - Right boundary index
40     * @returns Array with [distance, index1, index2]
41     */
42    const divideAndConquer = (left: number, right: number): number[] => {
43        // Base case: no valid pair in range
44        if (left >= right) {
45            return [1 << 30, -1, -1]; // Return maximum distance as sentinel
46        }
47      
48        // Find middle point for dividing
49        const mid = (left + right) >> 1;
50        const midX = pointsWithIndices[mid][0];
51      
52        // Recursively find closest pairs in left and right halves
53        let leftResult = divideAndConquer(left, mid);
54        let rightResult = divideAndConquer(mid + 1, right);
55      
56        // Choose the better result (smaller distance or lexicographically smaller indices)
57        if (
58            leftResult[0] > rightResult[0] ||
59            (leftResult[0] === rightResult[0] && 
60                (leftResult[1] > rightResult[1] || 
61                    (leftResult[1] === rightResult[1] && leftResult[2] > rightResult[2])))
62        ) {
63            leftResult = rightResult;
64        }
65      
66        // Find points within the strip around the dividing line
67        const stripPoints: number[][] = [];
68        for (let i = left; i <= right; ++i) {
69            // Only consider points within minimum distance from dividing line
70            if (Math.abs(pointsWithIndices[i][0] - midX) <= leftResult[0]) {
71                stripPoints.push(pointsWithIndices[i]);
72            }
73        }
74      
75        // Sort strip points by y-coordinate
76        stripPoints.sort((a, b) => a[1] - b[1]);
77      
78        // Check pairs within the strip
79        for (let i = 0; i < stripPoints.length; ++i) {
80            for (let j = i + 1; j < stripPoints.length; ++j) {
81                // If y-distance exceeds minimum, no need to check further
82                if (stripPoints[j][1] - stripPoints[i][1] > leftResult[0]) {
83                    break;
84                }
85              
86                // Ensure indices are in ascending order
87                const firstIndex = Math.min(stripPoints[i][2], stripPoints[j][2]);
88                const secondIndex = Math.max(stripPoints[i][2], stripPoints[j][2]);
89              
90                // Calculate Manhattan distance between points
91                const distance = dist(
92                    stripPoints[i][0], stripPoints[i][1], 
93                    stripPoints[j][0], stripPoints[j][1]
94                );
95              
96                // Update result if better pair found
97                if (distance < leftResult[0] || 
98                    (distance === leftResult[0] && 
99                        (firstIndex < leftResult[1] || 
100                            (firstIndex === leftResult[1] && secondIndex < leftResult[2])))) {
101                    leftResult = [distance, firstIndex, secondIndex];
102                }
103            }
104        }
105      
106        return leftResult;
107    };
108  
109    // Return the indices of the closest pair (exclude distance)
110    return divideAndConquer(0, arrayLength - 1).slice(1);
111}
112
113/**
114 * Calculates Manhattan distance between two points
115 * @param x1 - X-coordinate of first point
116 * @param y1 - Y-coordinate of first point
117 * @param x2 - X-coordinate of second point
118 * @param y2 - Y-coordinate of second point
119 * @returns Manhattan distance between the points
120 */
121function dist(x1: number, y1: number, x2: number, y2: number): number {
122    return Math.abs(x1 - x2) + Math.abs(y1 - y2);
123}
124
125/**
126 * Creates a hash value from two coordinates
127 * @param x - X-coordinate
128 * @param y - Y-coordinate
129 * @returns Combined hash value
130 */
131function f(x: number, y: number): number {
132    return x * 100000 + y;
133}
134

Time and Space Complexity

Time Complexity: O(n log n * log n) where n is the length of the input arrays.

The algorithm uses a divide-and-conquer approach similar to the closest pair of points problem:

  • Initial sorting of points takes O(n log n)
  • The recursive function dfs divides the problem into two halves, creating O(log n) levels of recursion
  • At each recursion level, the merging step examines points within distance d1 from the dividing line:
    • Filtering points near the dividing line: O(n) across all recursive calls at each level
    • Sorting the filtered points by y-coordinate: O(k log k) where k is the number of filtered points
    • The nested loops to check distances between filtered points: Due to the geometric property that at most 8 points can be within distance d1 in the strip, this is O(k)
  • Since the filtering and processing happens at each of the O(log n) levels, and each level processes O(n) points total with O(log n) sorting overhead in worst case, the overall time complexity is O(n log n * log n)

Space Complexity: O(n)

  • The points array stores all n points with their indices: O(n)
  • The pl dictionary stores point-to-index mappings: O(n) in worst case
  • The recursion stack depth is O(log n)
  • The temporary array t in each recursive call can contain at most O(n) points across all recursive calls at the same level
  • Overall space complexity is dominated by the linear storage requirements: O(n)

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

Common Pitfalls

1. Incorrect Handling of Lexicographic Ordering When Comparing Pairs

One of the most common pitfalls in this problem is incorrectly comparing pairs for lexicographic ordering, especially when distances are equal. The comparison logic can become convoluted and error-prone.

Pitfall Example:

# Incorrect comparison - easy to mess up the logic
if dist_left > dist_right or (dist_left == dist_right and 
    (idx_i_left > idx_i_right or (idx_i_left == idx_i_right and idx_j_left > idx_j_right))):

Solution: Create a helper function or use tuples for cleaner comparison:

def is_better_pair(dist1, i1, j1, dist2, i2, j2):
    """Returns True if pair1 is better than pair2"""
    if dist1 != dist2:
        return dist1 < dist2
    return (i1, j1) < (i2, j2)  # Tuple comparison handles lexicographic ordering naturally

2. Strip Width Optimization Issue

The algorithm filters points in the strip based on x-coordinate distance from the middle line. However, using the wrong distance threshold can lead to missing valid pairs or inefficient checking.

Pitfall Example:

# Using wrong variable or incorrect threshold
strip_points = [p for p in points[left:right + 1] if abs(p[0] - mid_x) <= dist_left]

Solution: Ensure you're using the current minimum distance and not mixing up variable names:

current_min_dist = min(dist_left, dist_right)  # Use the actual minimum
strip_points = [p for p in points[left:right + 1] if abs(p[0] - mid_x) <= current_min_dist]

3. Index Management Confusion

The algorithm works with both original indices and positions in the sorted array. Mixing these up is a common source of bugs.

Pitfall Example:

# Forgetting to sort indices before returning
idx_i, idx_j = strip_points[i][2], strip_points[j][2]  # These might not be in order!
return [idx_i, idx_j]  # Could violate i < j requirement

Solution: Always ensure indices are properly ordered before any comparison or return:

idx_i, idx_j = strip_points[i][2], strip_points[j][2]
if idx_i > idx_j:
    idx_i, idx_j = idx_j, idx_i  # Ensure i < j
# Or more concisely:
idx_i, idx_j = sorted([strip_points[i][2], strip_points[j][2]])

4. Duplicate Points Early Return Bug

When checking for duplicate points, returning immediately after finding the first duplicate can miss lexicographically smaller pairs.

Pitfall Example:

for i, (x, y) in enumerate(zip(nums1, nums2)):
    if len(point_indices[(x, y)]) > 1:
        return [i, point_indices[(x, y)][1]]  # Might not be the smallest pair!

Solution: Collect all duplicate pairs first and return the lexicographically smallest:

duplicate_pairs = []
for coords, indices in point_indices.items():
    if len(indices) > 1:
        # Generate all pairs from duplicate points
        for i in range(len(indices)):
            for j in range(i + 1, len(indices)):
                duplicate_pairs.append((indices[i], indices[j]))

if duplicate_pairs:
    duplicate_pairs.sort()  # Sort lexicographically
    return list(duplicate_pairs[0])

5. Y-Coordinate Pruning Boundary Error

When checking pairs in the strip sorted by y-coordinate, the pruning condition can be off by one or use the wrong comparison.

Pitfall Example:

if strip_points[j][1] - strip_points[i][1] >= dist_left:  # Should be > not >=
    break

Solution: Use strict inequality for the pruning condition:

if strip_points[j][1] - strip_points[i][1] > current_min_dist:
    break  # Points further apart in y-direction can't be closer

These pitfalls highlight the importance of careful index management, proper comparison logic, and understanding the geometric properties of the Manhattan distance when implementing the divide-and-conquer closest pair algorithm.

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

Which algorithm should you use to find a node that is close to the root of the tree?

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

Divide and Conquer Intro

https assets algo monster cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger problem using the solutions

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

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

Load More