202609141742 Leetcode Number of Perfect Pairs

#project

Problem

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.

Note: The absolute value |x| refers to the non-negative value of x.

Example 1:

Input: nums = [0,1,2,3]
Output: 2
Explanation:
There are 2 perfect pairs

Input: nums = [-3,2,-1,4]
Output: 4
Explanation:
There are 4 perfect pairs

**Input:** nums = [1,10,100,1000]
**Output:** 0
**Explanation:**
There are no perfect pairs. Thus, the answer is 0.

pub fn perfect_pairs(nums: Vec<i32>) -> i64 {
    let mut count = 0;
    for i in 0..(nums.len() - 1) {
        for j in (i + 1)..nums.len() {
            let a = &nums[i];
            let b = &nums[j];
            if min((a - b).abs(), (a + b).abs()) <= min(a.abs(), b.abs())
                && max((a - b).abs(), (a + b).abs()) >= max(a.abs(), b.abs())
            {
                count += 1;
            }
        }
    }
    count
}

This shows us that all of our scenarios simplify to one of two situations depending on which number is greater. Therefore, if we order the array before searching it, we can simplify all the comparisons down to b - a <= a because we know that b >= a. This simplifies a lot of arithmetic work to a very quick operation.

pub fn perfect_pairs(nums: Vec<i32>) -> i64 {
    let mut abs_vals: Vec<i32> = nums.iter().map(|n| n.abs()).collect();
    abs_vals.sort_unstable();

    let mut count = 0;
    for i in 0..abs_vals.len() {
        for j in (i + 1)..abs_vals.len() {
            if abs_vals[j] - abs_vals[i] <= abs_vals[i] {
                count += 1;
            } else {
                break;
            }
        }
    }

    count
}

However, this (and breaking early) is still not fast enough. We have an $O\left(n^2\right)$ solution in the worst case still and given we might have 10^5 values in nums, that's not going to be good enough.

Instead we need to find the way to get to $O(n\cdot \log n)$ or $O\left(n\right)$ algorithm itself. The answer is the common "sliding window" approach with two pointers. We fix a given i in the sorted, absolute values of the numbers for one of the pointers. Then we make sure that we're at least looking at the next number (j = j.max(i + 1)) in case i "catches up" to j as we move them. Then we do the core loop of value checking (which is now fast) and advancing j. All of those values will be valid so then we add the full range of valid values as a single arithmetic count. Then we advance i and go from there.

pub fn perfect_pairs(nums: Vec<i32>) -> i64 {
    let mut abs_vals: Vec<i32> = nums.iter().map(|n| n.abs()).collect();
    abs_vals.sort_unstable();

    let mut j = 0;
    let mut count: i64 = 0;
    for i in 0..abs_vals.len() {
        j = j.max(i + 1);
        while j < abs_vals.len() && abs_vals[j] - abs_vals[i] <= abs_vals[i] {
            j += 1;
        }
        count += (j - i - 1) as i64;
    }

    count
}