Beautiful Pairs

Problem

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.

Examples

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 <= 10^5
• nums1.length == nums2.length
• 0 <= nums1i <= nums1.length
• 0 <= nums2i <= nums2.length

Solution

Method 1 – Sorting with Coordinate Transformation and Ordered Set

Intuition

The Manhattan distance |a-b|+|c-d| can be minimized by sorting points and checking nearby points. By transforming coordinates and using an ordered set (like TreeSet or SortedList), we can efficiently find the closest pair.

Approach

1. For each index, create a tuple (nums1[i], nums2[i], i).
2. Sort the tuples by nums1, then nums2, then index.
3. Use an ordered set to keep track of seen points by nums2 and their indices.
4. For each point, check the closest in the set (by nums2) to minimize the sum of differences.
5. Track the minimum distance and the lexicographically smallest pair.
6. Return the answer.

Code

C++

#include <set>
class Solution {
public:
    vector<int> beautifulPair(vector<int>& a, vector<int>& b) {
        int n = a.size(), minDist = INT_MAX;
        vector<tuple<int,int,int>> pts;
        for (int i = 0; i < n; ++i) pts.push_back({a[i], b[i], i});
        sort(pts.begin(), pts.end());
        set<pair<int,int>> s;
        vector<int> ans = {0, 1};
        for (auto& [x, y, i] : pts) {
            auto it = s.lower_bound({y, -1});
            for (int d = -1; d <= 0; ++d) {
                auto jt = it;
                if (d == -1 && jt != s.begin()) --jt;
                if (jt != s.end()) {
                    int j = jt->second;
                    int dist = abs(a[i]-a[j]) + abs(b[i]-b[j]);
                    if (i > j && (dist < minDist || (dist == minDist && make_pair(j,i) < make_pair(ans[0],ans[1])))) {
                        minDist = dist;
                        ans = {j, i};
                    }
                }
            }
            s.insert({y, i});
        }
        return ans;
    }
};

Go

func beautifulPair(a, b []int) []int {
    n := len(a)
    type pt struct{ x, y, i int }
    pts := make([]pt, n)
    for i := 0; i < n; i++ {
        pts[i] = pt{a[i], b[i], i}
    }
    sort.Slice(pts, func(i, j int) bool {
        if pts[i].x != pts[j].x { return pts[i].x < pts[j].x }
        if pts[i].y != pts[j].y { return pts[i].y < pts[j].y }
        return pts[i].i < pts[j].i
    })
    ans := []int{0, 1}
    minDist := 1<<31 - 1
    s := map[int]int{}
    for _, p := range pts {
        for y, j := range s {
            dist := abs(a[p.i]-a[j]) + abs(b[p.i]-b[j])
            if p.i > j && (dist < minDist || (dist == minDist && (j < ans[0] || (j == ans[0] && p.i < ans[1])))) {
                minDist = dist
                ans = []int{j, p.i}
            }
        }
        s[p.y] = p.i
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }

Java

import java.util.*;
class Solution {
    public int[] beautifulPair(int[] a, int[] b) {
        int n = a.length, minDist = Integer.MAX_VALUE;
        int[] ans = {0, 1};
        List<int[]> pts = new ArrayList<>();
        for (int i = 0; i < n; ++i) pts.add(new int[]{a[i], b[i], i});
        pts.sort((p, q) -> p[0]!=q[0]?p[0]-q[0]:p[1]!=q[1]?p[1]-q[1]:p[2]-q[2]);
        TreeMap<Integer, Integer> s = new TreeMap<>();
        for (int[] p : pts) {
            for (int y : s.keySet()) {
                int j = s.get(y);
                int dist = Math.abs(a[p[2]]-a[j]) + Math.abs(b[p[2]]-b[j]);
                if (p[2] > j && (dist < minDist || (dist == minDist && (j < ans[0] || (j == ans[0] && p[2] < ans[1]))))) {
                    minDist = dist;
                    ans = new int[]{j, p[2]};
                }
            }
            s.put(p[1], p[2]);
        }
        return ans;
    }
}

Kotlin

class Solution {
    fun beautifulPair(a: IntArray, b: IntArray): IntArray {
        val n = a.size
        val pts = Array(n) { i -> Triple(a[i], b[i], i) }
        pts.sortWith(compareBy({ it.first }, { it.second }, { it.third }))
        var ans = intArrayOf(0, 1)
        var minDist = Int.MAX_VALUE
        val s = sortedMapOf<Int, Int>()
        for ((x, y, i) in pts) {
            for ((yy, j) in s) {
                val dist = kotlin.math.abs(a[i]-a[j]) + kotlin.math.abs(b[i]-b[j])
                if (i > j && (dist < minDist || (dist == minDist && (j < ans[0] || (j == ans[0] && i < ans[1]))))) {
                    minDist = dist
                    ans = intArrayOf(j, i)
                }
            }
            s[y] = i
        }
        return ans
    }
}

Python

class Solution:
    def beautifulPair(self, a: list[int], b: list[int]) -> list[int]:
        n = len(a)
        pts = sorted((a[i], b[i], i) for i in range(n))
        ans = [0, 1]
        min_dist = float('inf')
        from bisect import bisect_left, insort
        s = []
        for x, y, i in pts:
            for yy, j in s:
                dist = abs(a[i]-a[j]) + abs(b[i]-b[j])
                if i > j and (dist < min_dist or (dist == min_dist and (j < ans[0] or (j == ans[0] and i < ans[1])))):
                    min_dist = dist
                    ans = [j, i]
            insort(s, (y, i))
        return ans

Rust

impl Solution {
    pub fn beautiful_pair(a: Vec<i32>, b: Vec<i32>) -> Vec<i32> {
        let n = a.len();
        let mut pts: Vec<(i32, i32, usize)> = (0..n).map(|i| (a[i], b[i], i)).collect();
        pts.sort();
        let mut ans = vec![0, 1];
        let mut min_dist = i32::MAX;
        let mut s: Vec<(i32, usize)> = vec![];
        for &(x, y, i) in &pts {
            for &(yy, j) in &s {
                let dist = (a[i]-a[j]).abs() + (b[i]-b[j]).abs();
                if i > j && (dist < min_dist || (dist == min_dist && (j < ans[0] as usize || (j == ans[0] as usize && i < ans[1] as usize)))) {
                    min_dist = dist;
                    ans = vec![j as i32, i as i32];
                }
            }
            s.push((y, i));
        }
        ans
    }
}

Complexity

• ⏰ Time complexity: O(n log n + n^2) (with ordered set, can be improved to O(n log n) with advanced data structures)
• 🧺 Space complexity: O(n)