LeetCode 3649 - Number of Perfect Pairs

LeetCode Problem 3649

Difficulty: 🟡 Medium
Topics: Array, Math, Two Pointers, Sorting

Solution

Problem Understanding

We are given an integer array nums and must count how many index pairs (i, j) with i < j are perfect.

For each pair, let:

a = nums[i]
b = nums[j]

The pair is considered perfect if both of the following conditions hold:

min(|a - b|, |a + b|) <= min(|a|, |b|)
max(|a - b|, |a + b|) >= max(|a|, |b|)

The input may contain positive numbers, negative numbers, and zero. The output is the number of index pairs satisfying the definition.

The constraints are large:

2 <= n <= 100000
|nums[i]| <= 10^9

A quadratic solution that checks every pair would require roughly 10^10 comparisons in the worst case, which is far too slow. We need an algorithm around O(n log n) or better.

Several edge cases are important:

Negative numbers matter because the conditions involve both |a - b| and |a + b|.
Zero values require special attention because inequalities involving minimum absolute values can become very restrictive.
Duplicate values must be counted correctly because the problem asks for distinct index pairs, not distinct values.
Very large absolute values require care when multiplying by 2, although both Python and Go can safely handle the required range with 64-bit integers.

Approaches

Brute Force

The most direct approach is to examine every pair (i, j).

For each pair:

Compute |a - b|.
Compute |a + b|.
Compute the required minimums and maximums.
Check whether both inequalities hold.
Increment the answer if they do.

This approach is obviously correct because it directly implements the definition of a perfect pair.

However, there are O(n²) pairs. With n = 100000, this becomes approximately five billion pairs, which is completely infeasible.

Key Observation

The entire problem becomes much simpler after applying two identities.

Let:

x = |a|
y = |b|

A well-known identity states:

$$\min(|a-b|, |a+b|) = ||a| - |b||$$

Another identity states:

$$\max(|a-b|, |a+b|) = |a| + |b|$$

Substituting these into the problem:

$$||a|-|b|| \le \min(|a|,|b|)$$

and

$$|a|+|b| \ge \max(|a|,|b|)$$

The second inequality is always true because the sum of two non-negative numbers is always at least as large as either one individually.

Therefore the entire problem reduces to:

$$||a|-|b|| \le \min(|a|,|b|)$$

Let:

$$x = |a|,\quad y = |b|$$

Assume without loss of generality that x <= y.

Then:

$$|x-y| = y-x$$

and

$$\min(x,y)=x$$

So the condition becomes:

$$y-x \le x$$

which simplifies to:

$$y \le 2x$$

Therefore a pair is perfect if and only if:

$$\max(|a|,|b|) \le 2 \cdot \min(|a|,|b|)$$

Now the problem becomes:

Count pairs of absolute values whose larger value is at most twice the smaller value.

After converting every element to its absolute value and sorting, a classic two-pointer technique can count such pairs efficiently.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Checks every pair directly
Optimal	O(n log n)	O(n)	Sort absolute values and count valid ranges with two pointers

Algorithm Walkthrough

Step 1: Convert all numbers to absolute values

The derived condition depends only on |a| and |b|.

Create an array:

absNums[i] = |nums[i]|

Step 2: Sort the absolute values

Sort absNums in non-decreasing order.

After sorting, if i < j, then:

absNums[i] <= absNums[j]

This lets us treat absNums[i] as the smaller value and absNums[j] as the larger value.

Step 3: Maintain a sliding right boundary

For each left index i, we want all positions j > i satisfying:

absNums[j] <= 2 * absNums[i]

Because the array is sorted, all valid indices form one contiguous range.

Use a pointer right that only moves forward.

Step 4: Expand the right boundary

While:

right < n
and absNums[right] <= 2 * absNums[i]

advance right.

When the loop stops:

[i + 1, right - 1]

are exactly the valid partners for index i.

Step 5: Count the pairs

The number of valid partners for i is:

(right - i - 1)

Add this value to the answer.

Step 6: Continue for every index

Since right never moves backward, the total work after sorting is linear.

Why it works

After the algebraic simplification, a pair is perfect exactly when the larger absolute value is at most twice the smaller absolute value. Sorting places all potential partners for a fixed left value into a contiguous interval. The two-pointer technique finds the maximal valid interval for every index and counts all pairs inside it. Since every valid pair is counted exactly once and every counted pair satisfies the derived condition, the algorithm is correct.

Python Solution

from typing import List

class Solution:
    def perfectPairs(self, nums: List[int]) -> int:
        values = sorted(abs(x) for x in nums)
        n = len(values)

        answer = 0
        right = 0

        for left in range(n):
            if right < left + 1:
                right = left + 1

            while right < n and values[right] <= 2 * values[left]:
                right += 1

            answer += right - left - 1

        return answer

The implementation begins by converting every element to its absolute value and sorting the resulting array. This reflects the mathematical reduction that shows only absolute values matter.

The variable right represents the first index that is no longer valid for the current left. For each position left, the inner loop advances right until the condition values[right] <= 2 * values[left] fails.

Because the array is sorted, every index between left + 1 and right - 1 forms a valid perfect pair with left. The count of such indices is right - left - 1.

The crucial optimization is that right never moves backward. Across the entire algorithm, it advances at most n times, giving linear work after sorting.

Go Solution

package main

import "sort"

func perfectPairs(nums []int) int64 {
	values := make([]int64, len(nums))

	for i, x := range nums {
		if x < 0 {
			x = -x
		}
		values[i] = int64(x)
	}

	sort.Slice(values, func(i, j int) bool {
		return values[i] < values[j]
	})

	n := len(values)
	var answer int64 = 0
	right := 0

	for left := 0; left < n; left++ {
		if right < left+1 {
			right = left + 1
		}

		for right < n && values[right] <= 2*values[left] {
			right++
		}

		answer += int64(right - left - 1)
	}

	return answer
}

The Go solution follows exactly the same algorithm. The primary implementation detail is the use of int64 for the absolute values and the answer. Although the input bounds fit comfortably inside 32-bit integers, using int64 guarantees that the multiplication by 2 and the pair count remain safe.

Go slices are used directly after sorting with sort.Slice, and no additional data structures are required.

Worked Examples

Example 1

Input:

nums = [0,1,2,3]

Absolute values:

[0,1,2,3]

Sorted:

[0,1,2,3]

left	value	right after expansion	pairs added
0	0	1	0
1	1	3	1
2	2	4	1
3	3	4	0

Total:

0 + 1 + 1 + 0 = 2

Answer:

Example 2

Input:

nums = [-3,2,-1,4]

Absolute values:

[3,2,1,4]

Sorted:

[1,2,3,4]

left	value	right after expansion	pairs added
0	1	2	1
1	2	4	2
2	3	4	1
3	4	4	0

Total:

1 + 2 + 1 + 0 = 4

Answer:

Example 3

Input:

nums = [1,10,100,1000]

Absolute values:

[1,10,100,1000]

Sorted:

[1,10,100,1000]

left	value	right after expansion
0	1	1
1	10	2
2	100	3
3	1000	4

Total:

Answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Stores the absolute-value array

The two-pointer scan itself is linear because the right pointer only moves forward. Therefore the total runtime is O(n log n) due to sorting. The auxiliary space is O(n) for storing the absolute values.

Test Cases

sol = Solution()

assert sol.perfectPairs([0, 1, 2, 3]) == 2          # example 1
assert sol.perfectPairs([-3, 2, -1, 4]) == 4        # example 2
assert sol.perfectPairs([1, 10, 100, 1000]) == 0    # example 3

assert sol.perfectPairs([0, 0]) == 1               # two zeros
assert sol.perfectPairs([0, 5]) == 0               # zero with non-zero
assert sol.perfectPairs([5, 5]) == 1               # equal values
assert sol.perfectPairs([-5, 5]) == 1              # same absolute value

assert sol.perfectPairs([1, 2]) == 1               # boundary ratio exactly 2
assert sol.perfectPairs([1, 3]) == 0               # ratio greater than 2

assert sol.perfectPairs([1, 2, 4]) == 2            # chain of valid pairs
assert sol.perfectPairs([1, 2, 4, 8]) == 3         # multiple boundaries

assert sol.perfectPairs([-1, -2, -4, -8]) == 3     # all negatives

assert sol.perfectPairs([7, 7, 7, 7]) == 6         # all pairs valid

assert sol.perfectPairs([1, 1, 2, 2]) == 6         # duplicates

assert sol.perfectPairs([10**9, 10**9]) == 1       # large values
assert sol.perfectPairs([-10**9, 10**9]) == 1      # large opposite signs

Test Summary

Test	Why
`[0,1,2,3]`	Official example
`[-3,2,-1,4]`	Official example with mixed signs
`[1,10,100,1000]`	Official example with no valid pairs
`[0,0]`	Zero handling
`[0,5]`	Zero cannot pair with non-zero
`[5,5]`	Equal values
`[-5,5]`	Same absolute value, opposite signs
`[1,2]`	Exact boundary condition
`[1,3]`	Just beyond boundary
`[1,2,4]`	Multiple overlapping valid pairs
`[1,2,4,8]`	Sliding-window behavior
`[-1,-2,-4,-8]`	Negative-only input
`[7,7,7,7]`	All pairs valid
`[1,1,2,2]`	Duplicate values
`[10^9,10^9]`	Large magnitude values
`[-10^9,10^9]`	Large values with opposite signs

Edge Cases

Arrays Containing Zero

Zero is the most subtle value in this problem. After simplification, the condition becomes:

$$\max(x,y) \le 2\min(x,y)$$

If one value is zero and the other is positive, the right side becomes zero while the left side is positive, making the condition impossible. Therefore zero can only form a perfect pair with another zero. The sorted two-pointer solution handles this naturally because 0 <= 2 * 0 is true, while any positive value fails the condition.

Duplicate Values

When many identical absolute values exist, every pair among them is valid because:

$$x \le 2x$$

A common bug is undercounting duplicates by treating values instead of indices. Our algorithm counts index pairs directly through range sizes, so duplicates are handled correctly.

Extremely Large Values

The input allows values up to 10^9. The condition requires checking:

value[j] <= 2 * value[i]

In Python this is automatically safe because integers have arbitrary precision. In Go, using int64 ensures the multiplication remains safe and avoids any overflow concerns.