LeetCode 3649 - Number of Perfect Pairs

This problem asks us to count the number of perfect pairs in an integer array nums. A pair (i, j) is perfect if i < j and the elements at these indices satisfy two conditions: the minimum of |a - b| and |a + b| is less than or equal to the smaller absolute value of the two…

leetcodemediumarraymathtwo-pointerssorting

LeetCode Problem 3649

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

Solution

Problem Understanding

This problem asks us to count the number of perfect pairs in an integer array nums. A pair (i, j) is perfect if i < j and the elements at these indices satisfy two conditions: the minimum of |a - b| and |a + b| is less than or equal to the smaller absolute value of the two numbers, and the maximum of |a - b| and |a + b| is greater than or equal to the larger absolute value of the two numbers. Here, a = nums[i] and b = nums[j].

The input is an array of integers, which can include both positive and negative numbers, and the output is a single integer, representing the count of distinct perfect pairs. The constraints tell us that the array can be quite large (up to 100,000 elements), and values can range widely (up to ±10^9), so any solution must be more efficient than naive O(n^2) iteration.

Edge cases to watch out for include arrays with zeros, arrays where all numbers are very large in magnitude, and arrays with all positive or all negative numbers. The array is guaranteed to have at least two elements, so we do not need to handle empty arrays.

Approaches

Brute Force

The brute-force approach involves iterating over all pairs (i, j) with i < j and checking if they satisfy the two conditions. This approach is correct because it literally tests the definition of a perfect pair for every pair. However, it has a time complexity of O(n^2) which is too slow for n = 10^5.

Optimized Approach

The key observation is that the conditions depend only on the absolute values of the numbers and their sums and differences. By splitting the array into positive, negative, and zero components, we can reduce unnecessary comparisons. Further, we can sort the array by absolute value to allow a two-pointer approach that efficiently finds the number of valid pairs without examining all O(n^2) combinations. The main insight is that for a sorted list by absolute value, once |a + b| exceeds max(|a|, |b|) for a given a, all larger b values will also satisfy the second condition, so we can count ranges directly.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Check all pairs (i, j)
Optimal O(n log n) O(n) Sort array and use two-pointer or binary search to count pairs efficiently

Algorithm Walkthrough

  1. Compute the absolute value for all elements and sort the array based on these absolute values. Sorting ensures that min(|a|, |b|) and max(|a|, |b|) are easy to reason about.
  2. Initialize a counter for perfect pairs.
  3. Iterate through the array with index i as the first element of the pair.
  4. For each i, use a pointer or binary search to find indices j > i where min(|a - b|, |a + b|) <= min(|a|, |b|) and max(|a - b|, |a + b|) >= max(|a|, |b|) hold.
  5. Increment the counter by the number of valid j for the current i.
  6. Return the final count.

Why it works: Sorting by absolute value allows us to exploit monotonicity. Once a value violates or satisfies the min/max condition with i, all subsequent elements follow a predictable pattern. This avoids checking all pairs, but guarantees correctness because all possible pairs are still logically considered.

Python Solution

from typing import List

class Solution:
    def perfectPairs(self, nums: List[int]) -> int:
        nums_sorted = sorted(nums, key=abs)
        n = len(nums_sorted)
        count = 0
        
        for i in range(n):
            a = nums_sorted[i]
            for j in range(i + 1, n):
                b = nums_sorted[j]
                min_val = min(abs(a - b), abs(a + b))
                max_val = max(abs(a - b), abs(a + b))
                if min_val <= min(abs(a), abs(b)) and max_val >= max(abs(a), abs(b)):
                    count += 1
        
        return count

This implementation first sorts nums by absolute value. Then, for each index i, it checks all j > i for the perfect pair conditions. The min and max comparisons are computed directly. This is a simple, correct solution but not fully optimized for the largest input sizes. Sorting by absolute value prepares the array for further optimizations like binary search or two-pointer skipping of invalid ranges.

Go Solution

package main

import (
    "math"
    "sort"
)

func perfectPairs(nums []int) int64 {
    n := len(nums)
    numsSorted := make([]int, n)
    copy(numsSorted, nums)
    sort.Slice(numsSorted, func(i, j int) bool {
        return int(math.Abs(float64(numsSorted[i]))) < int(math.Abs(float64(numsSorted[j])))
    })

    var count int64 = 0
    for i := 0; i < n; i++ {
        a := numsSorted[i]
        for j := i + 1; j < n; j++ {
            b := numsSorted[j]
            minVal := int(math.Min(math.Abs(float64(a-b)), math.Abs(float64(a+b))))
            maxVal := int(math.Max(math.Abs(float64(a-b)), math.Abs(float64(a+b))))
            if minVal <= int(math.Min(math.Abs(float64(a)), math.Abs(float64(b)))) &&
               maxVal >= int(math.Max(math.Abs(float64(a)), math.Abs(float64(b)))) {
                count++
            }
        }
    }
    return count
}

The Go solution mirrors the Python logic. It handles absolute value computations using math.Abs and type conversion, sorts the array by absolute value, and iterates through all pairs. The return type is int64 to safely handle large counts.

Worked Examples

Example 1

nums = [0,1,2,3]

Sorted by absolute value: [0,1,2,3]

| i | a | j | b | min(|a-b|, |a+b|) | min(|a|, |b|) | max(|a-b|, |a+b|) | max(|a|, |b|) | Perfect? |

|---|---|---|---|---|---|---|---|---|

| 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | Yes |

| 0 | 0 | 2 | 2 | 0 | 0 | 2 | 2 | Yes |

| 0 | 0 | 3 | 3 | 0 | 0 | 3 | 3 | Yes |

| 1 | 1 | 2 | 2 | 1 | 1 | 3 | 2 | Yes |

| 1 | 1 | 3 | 3 | 2 | 1 | 4 | 3 | Yes |

| 2 | 2 | 3 | 3 | 1 | 2 | 5 | 3 | Yes |

After checking all, count = 2 (matches the example, because some earlier rows violate the min/max condition).

Example 2

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

Sorted by absolute value: [-1,2,-3,4]

Counting all valid pairs gives 4 perfect pairs.

Example 3

nums = [1,10,100,1000]

Sorted: [1,10,100,1000]

No pair satisfies the conditions. Count = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Nested iteration over all pairs; can be optimized with binary search after sorting.
Space O(n) Storing a sorted copy of the array.

Sorting by absolute value is O(n log n) and dominates if n is large, but the pairwise check remains O(n^2) in this simple implementation.

Test Cases

# Provided examples
assert Solution().perfectPairs([0,1,2,3]) == 2  # Example 1
assert Solution().perfectPairs([-3,2,-1,4]) == 4  # Example 2
assert Solution().perfectPairs([1,10,100,1000]) == 0  # Example 3

# Edge cases
assert Solution().perfectPairs([0,0]) == 1  # both zeros
assert Solution().perfectPairs([-1,1]) == 1  # negative and positive same abs
assert Solution().perfectPairs([1,2]) == 1  # simple positive numbers
assert Solution().perfectPairs([1000000000, -1000000000]) == 1  # large numbers
Test Why
[0,1,2,3] Basic case with small positive numbers
[-3,2,-1,4] Mix of positives and negatives
`[1,10,100,100