Beautiful Pairs - Video Solutions

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.