Number of perfect pairs

Array Math Two Pointers Sorting

33.4% acceptance

Feb 25, 2026

You are given an integer array nums. A pair of indices (i, j) is called perfect if the following conditions are satisfied: i < j Let a = nums[i], b = nums[j]. Then: min(|a - b|, |a + b|) <= min(|a|, |b|) max(|a - b|, |a + b|) >= max(|a|, |b|) Return the number of distinct perfect pairs.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn perfect_pairs(nums: Vec<i32>) -> i64 {
    // Analyze conditions:
    // Let a, b denote nums[i], nums[j] (values, sign doesn't matter for abs).
    // Let x = |a|, y = |b|, assume x <= y (WLOG, symmetric).
    // min(|a-b|, |a+b|):
    //   If same sign: |a-b| <= |a+b|, so min = |a-b| = y-x
    //   If opposite sign: |a+b| <= |a-b|, so min = |a+b| = y-x (since |a+b| = ||a|-|b||)
    //   Either way, min(|a-b|, |a+b|) = |x - y| = y - x (since x <= y).
    // max(|a-b|, |a+b|):
    //   Similar analysis: max = x + y.
    //
    // Conditions:
    // 1) min(|a-b|, |a+b|) <= min(|a|, |b|) => y - x <= x => y <= 2x
    // 2) max(|a-b|, |a+b|) >= max(|a|, |b|) => x + y >= y => x >= 0, always true!
    //
    // So the conditions reduce to:
    // y <= 2x, where x = min(|a|, |b|), y = max(|a|, |b|).
    // i.e., max(|a|, |b|) <= 2 * min(|a|, |b|).
    //
    // Special case: if x = 0 (one of them is 0):
    //   min = 0, y <= 2*0 = 0, so y = 0. Both must be 0.
    //
    // So: count pairs (i<j) where max(|a|, |b|) <= 2 * min(|a|, |b|).
    // Equivalently: |a| <= 2|b| AND |b| <= 2|a|.
    // i.e., 0.5 <= |a|/|b| <= 2 (when both nonzero).
    //
    // Plus: pairs where both are 0.
    
    let n = nums.len();
    let abs_vals: Vec<i64> = nums.iter().map(|&x| x.abs() as i64).collect();
    
    // Sort abs values to count pairs efficiently.
    let mut sorted = abs_vals.clone();
    sorted.sort_unstable();
    
    let mut count = 0i64;
    // Two pointers: for each i, find range of j where sorted[j] <= 2*sorted[i]
    // and sorted[i] <= 2*sorted[j] (automatically satisfied since sorted[j] >= sorted[i]).
    // But we need actual pair count, not just sorted pair count (preserve original indices).
    // Actually since we're counting unordered pairs: sort, then for each i find # j > i with sorted[j] <= 2*sorted[i].
    
    let mut right = 0usize;
    for i in 0..n {
      if right < i { right = i; }
      // Find largest index where sorted[r] <= 2 * sorted[i]
      while right + 1 < n && sorted[right + 1] <= 2 * sorted[i] {
        right += 1;
      }
      // Pairs: i with all j in (i, right]
      count += (right - i) as i64;
    }
    count
  }
}