Skip to main content
Talentd

Beautiful Pairs - Solution & Explanation

HardPremiumFree on FleetCodeArrayMathDivide and ConquerGeometry19 min read
Practice this problem

Problem Statement

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.
  • A pair of indices (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 <= 105
  • nums1.length == nums2.length
  • 0 <= nums1i <= nums1.length
  • 0 <= nums2i <= nums2.length

Approach Overview

Problem 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.

Solution

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

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair ComparisonO(n²)O(1)Useful for small inputs or verifying correctness during implementation
Sweep Line with Ordered SetO(n log n)O(n)Efficient practical approach when processing points incrementally
Sorting + Divide and ConquerO(n log n)O(n)Optimal solution for large datasets and typical interview expectation

Video Solution

Number of Good Pairs - Leetcode 1512 - Python • NeetCodeIO • 18,103 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Beautiful Pairs easy or hard?
Beautiful Pairs is classified as a Hard problem. It combines geometry, sorting, and divide-and-conquer optimization. Recognizing the closest-pair pattern and implementing it correctly is the main challenge.
Beautiful Pairs Python/Java solution
Most implementations follow the same algorithm: build a list of points with original indices, sort by x, then apply a divide-and-conquer closest pair routine. The FleetCode solution provides full implementations in Python, Java, C++, Go, and TypeScript with O(n log n) complexity.
How to solve Beautiful Pairs in O(n log n)?
First map each index to a point (nums1[i], nums2[i]) and sort points by x-coordinate. Apply a divide-and-conquer closest pair algorithm: recursively compute the best distance in each half and examine points in a narrow strip near the partition. Only nearby points need comparison, which keeps the total work at O(n log n).
What is the best approach for Beautiful Pairs?
The optimal solution uses a closest-pair-of-points technique with sorting and divide and conquer. After sorting points by x-coordinate, recursively compute the minimum distance in each half and check a small vertical strip for cross-boundary pairs. This reduces comparisons and achieves O(n log n) time complexity.
Is Beautiful Pairs asked at Google/Amazon/Meta?
Problems based on closest pair of points and Manhattan distance frequently appear in interviews at companies like Google and Meta. Variants involving sweep line or divide-and-conquer geometry are common in hard-level algorithm rounds.
What data structure is used in Beautiful Pairs?
Efficient solutions rely on sorted arrays, divide-and-conquer recursion, and sometimes an ordered set or balanced tree to maintain candidate points by y-coordinate. These structures allow fast pruning of points that cannot produce a smaller Manhattan distance.
What is the time complexity of Beautiful Pairs?
The brute force solution runs in O(n^2) time by checking every pair of points. Optimized approaches using a sweep line or divide and conquer reduce the complexity to O(n log n). Space complexity for the optimized methods is typically O(n) due to auxiliary structures and recursion.

Ready to solve this problem?

Practice Beautiful Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays