We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Beautiful Pairs

Number: 2719

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given two 0-indexed integer arrays nums1 and nums2 of the same length, think of each index i as defining a point (nums1[i], nums2[i]). A pair of indices (i, j) with i < j is called beautiful if the Manhattan distance |nums1[i] - nums1[j]| + |nums2[i] - nums2[j]| is as small as possible over all index pairs. In case of multiple pairs with the same minimum distance, return the lexicographically smallest pair (i.e. the one with the smallest i, and if tied then smallest j).

Key Insights

  • The distance metric is the Manhattan distance between points defined by corresponding elements in nums1 and nums2.
  • The problem becomes a “closest pair” in the L1 (Manhattan) metric, which has similarities to the well–known Euclidean closest pair problem.
  • A brute-force O(n²) solution is too slow for n up to 10⁵; hence an O(n log n) approach is needed.
  • A sweep-line (or divide and conquer) algorithm can be used. First, sort the points by one coordinate (e.g. by nums1 value), then maintain an “active set” ordered by the other coordinate (nums2) containing candidates within the current best distance.
  • When processing a new point, remove points from the active set whose x-coordinate difference exceeds the current best distance. Then, search only among points whose y-coordinate is within a band determined by the current best distance.
  • Don’t forget to update the answer with pair indices (in sorted order so that i < j) and, in case of ties, choose the lexicographically smallest one.

Space and Time Complexity

Time Complexity: O(n log n) on average, due to sorting the points and performing logarithmic insertions and removals from the balanced tree (or ordered set) for the sweep‐line. Space Complexity: O(n) for storing the points and the active set.

Solution

We can solve the problem by first representing each point as (x, y, index) where x = nums1[i] and y = nums2[i]. We then sort the list of points by x. As we sweep from left to right (in increasing x), we maintain an active set (ordered by y) that contains only the points that are “close enough” in x to possibly yield a Manhattan distance smaller than our current best distance. For each new point, we remove outdated points from the active set, then use binary search to quickly iterate only over those candidates whose y difference is no more than the current best distance. For each candidate in the active set with index value, we compute the Manhattan distance and update the best distance and best pair (making sure to output the pair in lexicographical order). We then insert the current point into the active set before proceeding.

The same logic is implemented in all four languages below using: • An array (sorted by x) for the points. • An “active set” ordered by y (achieved via binary search in Python and JavaScript, and via built‑in ordered data structures in C++ and Java). • Careful updating of both the best (minimum) Manhattan distance and the lexicographically smallest index pair in case of ties.

Code Solutions

# Python solution using a sweep line approach with bisect
import bisect
import math

def beautifulPairs(nums1, nums2):
    n = len(nums1)
    # Create points as tuples: (x, y, index)
    points = [(nums1[i], nums2[i], i) for i in range(n)]
    # sort points by x; if same x, then by y and index for determinism
    points.sort(key=lambda p: (p[0], p[1], p[2]))
    
    # active: list of (y, x, index) sorted by y
    active = []
    best_distance = math.inf
    best_pair = None  # store tuple (i, j)
    left = 0  # pointer for removal from active

    # helper to update best pair lexicographically
    def update_ans(i1, i2, d):
        nonlocal best_distance, best_pair
        # Ensure i1 < i2 for output
        pair = (min(i1, i2), max(i1, i2))
        if d < best_distance:
            best_distance = d
            best_pair = pair
        elif d == best_distance:
            # lexicographical comparison
            if best_pair is None or pair < best_pair:
                best_pair = pair

    # iterate through points sorted by x
    for p in points:
        x, y, idx = p
        # Remove points from active whose x difference is more than best_distance
        while left < len(points) and x - points[left][0] > best_distance:
            # remove from active set: need to delete the corresponding (y, x, index)
            rem_x, rem_y, rem_idx = points[left]
            # find (rem_y, rem_x, rem_idx) in active using binary search
            pos = bisect.bisect_left(active, (rem_y, rem_x, rem_idx))
            if pos < len(active) and active[pos] == (rem_y, rem_x, rem_idx):
                active.pop(pos)
            left += 1

        # In active, find candidates where |candidate_y - y| <= best_distance.
        lower_bound = (y - best_distance, -math.inf, -math.inf)
        upper_bound = (y + best_distance, math.inf, math.inf)
        start = bisect.bisect_left(active, lower_bound)
        # iterate over candidate points in active set that lie within the y band.
        for cand in active[start:]:
            cand_y, cand_x, cand_idx = cand
            if cand_y > y + best_distance:
                break
            # Calculate Manhattan distance
            d = abs(x - cand_x) + abs(y - cand_y)
            if d <= best_distance:
                update_ans(idx, cand_idx, d)

        # Insert current point into active set (maintaining order by y)
        bisect.insort(active, (y, x, idx))

    return list(best_pair) if best_pair is not None else []

# Example usage:
# print(beautifulPairs([1,2,3,2,4], [2,3,1,2,3]))
← Back to All Questions