You are given two 0-indexed integer arrays nums1 and nums2 of the same length. A pair of indices (i,j) is called beautiful if|nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| is the smallest amongst all possible indices pairs where i < j.
Return the beautiful pair. In the case that there are multiple beautiful pairs, return the lexicographically smallest pair.
Note that
|x| denotes the absolute value of x.(i1, j1) is lexicographically smaller than (i2, j2) if i1 < i2 or i1 == i2 and j1 < j2.
Example 1:
Input: nums1 = [1,2,3,2,4], nums2 = [2,3,1,2,3] Output: [0,3] Explanation: Consider index 0 and index 3. The value of |nums1[i]-nums1[j]| + |nums2[i]-nums2[j]| is 1, which is the smallest value we can achieve.
Example 2:
Input: nums1 = [1,2,4,3,2,5], nums2 = [1,4,2,3,5,1] Output: [1,4] Explanation: Consider index 1 and index 4. The value of |nums1[i]-nums1[j]| + |nums2[i]-nums2[j]| is 1, which is the smallest value we can achieve.
Constraints:
2 <= nums1.length, nums2.length <= 105nums1.length == nums2.length0 <= nums1i <= nums1.length0 <= nums2i <= nums2.lengthProblem Overview: You receive two arrays nums1 and nums2. Each index represents a point on a 2D plane: (nums1[i], nums2[i]). The task is to find two different indices i and j with the minimum Manhattan distance |x1 - x2| + |y1 - y2|. If multiple pairs share the same distance, return the lexicographically smallest pair of indices.
Approach 1: Brute Force Pair Comparison (O(n²) time, O(1) space)
The most direct strategy checks every pair of points. Iterate through all i, and for each j > i compute the Manhattan distance. Track the minimum distance and update the answer when a smaller value appears or when a tie produces a lexicographically smaller pair. This approach is simple and demonstrates the core idea, but it performs n(n−1)/2 comparisons. With large inputs, quadratic time becomes impractical.
Approach 2: Sweep Line with Ordered Set (O(n log n) time, O(n) space)
Treat the problem as a closest-pair search in geometry. First sort points by their x coordinate using sorting. Sweep from left to right while maintaining a balanced structure (like a TreeSet or ordered map) of candidate points sorted by y. Remove points whose x-distance already exceeds the current best distance. Then query nearby points in the ordered set whose y difference is within the best distance and compute Manhattan distances. This reduces comparisons dramatically because only nearby candidates are checked.
Approach 3: Sorting + Divide and Conquer (O(n log n) time, O(n) space)
This approach adapts the classic closest-pair-of-points algorithm. Sort points by x, then recursively split the array into left and right halves. Compute the minimum distance in each half, then examine the vertical strip around the midpoint where cross-boundary pairs could produce a smaller Manhattan distance. Points inside this strip are sorted by y, and only nearby neighbors need to be checked. The divide-and-conquer structure guarantees that each level processes linear work after the initial O(n log n) sorting step.
Handling ties requires storing original indices and comparing pairs lexicographically when distances match. Efficient implementations often combine geometric pruning with structures similar to an ordered set to maintain candidate points.
Recommended for interviews: Start by explaining the brute force method to show understanding of the Manhattan distance definition. Then move to the O(n log n) divide-and-conquer closest-pair technique. Interviewers expect candidates solving hard geometry problems to recognize this optimization pattern. The optimized solution demonstrates knowledge of computational geometry, sorting, and efficient spatial pruning.
This problem is equivalent to finding two points in the plane, such that the Manhattan distance between them is the smallest. If there are multiple points satisfying the condition, return the one with the smallest index.
First, we handle the case where there are duplicate points. For each point, we record the corresponding indices in a list. If the length of the index list is greater than 1, then the first two indices in the index list can be used as candidates, and we find the smallest index pair.
If there are no duplicate points, we sort all the points by x coordinates, and then use the divide and conquer to solve the problem.
For each interval [l, r], we first calculate the median of the x coordinates m, and then recursively solve the left and right intervals, and get d_1, (pi_1, pj_1) and d_2, (pi_2, pj_2) respectively, where d_1 and d_2 are the minimum Manhattan distances of the left and right intervals respectively, and (pi_1, pj_1) and (pi_2, pj_2) are the index pairs of the two points of the minimum Manhattan distance of the left and right intervals respectively. We take the smaller one of d_1 and d_2 as the minimum Manhattan distance of the current interval, and if d_1 = d_2, we take the one with the smaller index as the answer. The corresponding two points of the index are taken as the answer.
The above considers the case where the two points are on the same side. If the two points are on different sides, we take the middle point, i.e. the point with the index of m = \lfloor (l + r) / 2 \rfloor as the standard, and divide a new region. The range of this region is to expand the range of d_1 from the middle point to the left and right sides respectively. Then we sort these points in the range by y coordinates, and then traverse each point pair in the sorted order. If the difference of the y coordinates of the two points is greater than the current minimum Manhattan distance, then the following point pairs do not need to be considered, because their y coordinate differences are larger, so the Manhattan distance is larger, and it will not be smaller than the current minimum Manhattan distance. Otherwise, we update the minimum Manhattan distance, and update the answer.
Finally, we return the answer.
Time complexity: O(n times log n), where n is the length of the array.
Space complexity: O(n).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Comparison | O(n²) | O(1) | Useful for small inputs or verifying correctness during implementation |
| Sweep Line with Ordered Set | O(n log n) | O(n) | Efficient practical approach when processing points incrementally |
| Sorting + Divide and Conquer | O(n log n) | O(n) | Optimal solution for large datasets and typical interview expectation |
Number of Good Pairs - Leetcode 1512 - Python • NeetCodeIO • 18,103 views views
Watch 9 more video solutions →Practice Beautiful Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor