Beautiful pairs

Array Math Divide and Conquer Geometry Sorting Ordered Set

49.0% acceptance

Mar 31, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn beautiful_pair(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
    let n = nums1.len();
    let mut first_seen: HashMap<(i32, i32), usize> = HashMap::with_capacity(n);
    let mut duplicate_best: Option<(usize, usize)> = None;

    for i in 0..n {
      let point = (nums1[i], nums2[i]);
      if let Some(&first) = first_seen.get(&point) {
        let candidate = (first, i);
        if duplicate_best.is_none_or(|best| candidate < best) {
          duplicate_best = Some(candidate);
        }
      } else {
        first_seen.insert(point, i);
      }
    }

    if let Some((i, j)) = duplicate_best {
      return vec![i as i32, j as i32];
    }

    let mut pts: Vec<(i64, i64, usize)> = (0..n)
      .map(|i| (nums1[i] as i64 + nums2[i] as i64, nums1[i] as i64 - nums2[i] as i64, i))
      .collect();
    pts.sort();
    let (_, i, j) = Self::solve(&mut pts);
    vec![i as i32, j as i32]
  }

  fn solve(pts: &mut [(i64, i64, usize)]) -> (i64, usize, usize) {
    let n = pts.len();
    if n <= 3 {
      let mut best = (i64::MAX, usize::MAX, usize::MAX);
      for i in 0..n {
        for j in i+1..n {
          let d = (pts[i].0 - pts[j].0).abs().max((pts[i].1 - pts[j].1).abs());
          let (a, b) = if pts[i].2 < pts[j].2 { (pts[i].2, pts[j].2) } else { (pts[j].2, pts[i].2) };
          if (d, a, b) < best { best = (d, a, b); }
        }
      }
      pts.sort_by_key(|p| (p.1, p.0, p.2));
      return best;
    }
    let mid = n / 2;
    let mid_u = pts[mid].0;
    let left_best = Self::solve(&mut pts[..mid]);
    let right_best = Self::solve(&mut pts[mid..]);
    let mut best = if left_best <= right_best { left_best } else { right_best };
    let strip_limit = best.0;
    let mut merged = Vec::with_capacity(n);
    let (mut l, mut r) = (0, mid);
    while l < mid && r < n {
      if (pts[l].1, pts[l].0, pts[l].2) <= (pts[r].1, pts[r].0, pts[r].2) {
        merged.push(pts[l]); l += 1;
      } else {
        merged.push(pts[r]); r += 1;
      }
    }
    while l < mid { merged.push(pts[l]); l += 1; }
    while r < n { merged.push(pts[r]); r += 1; }
    pts.copy_from_slice(&merged);
    let strip: Vec<&(i64, i64, usize)> = pts.iter()
      .filter(|p| (p.0 - mid_u).abs() <= strip_limit)
      .collect();
    for i in 0..strip.len() {
      for j in i+1..strip.len() {
        if strip[j].1 - strip[i].1 > best.0 { break; }
        let dist = (strip[i].0 - strip[j].0).abs().max((strip[i].1 - strip[j].1).abs());
        let (a, b) = if strip[i].2 < strip[j].2 { (strip[i].2, strip[j].2) } else { (strip[j].2, strip[i].2) };
        if (dist, a, b) < best { best = (dist, a, b); }
      }
    }
    best
  }
}