Number of Perfect Pairs - Video Solutions
Number of Perfect Pairs | Leetcode 3649 | Q2 - Biweekly Contest 163
Number of Perfect Pairs - Video Solution
Watch 9 video solutions for Number of Perfect Pairs, a medium level problem involving Array, Math, Two Pointers. This walkthrough by ExpertFunda has 1,092 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
(i, j) |
(a, b) |
min(|a − b|, |a + b|) |
min(|a|, |b|) |
max(|a − b|, |a + b|) |
max(|a|, |b|) |
|---|---|---|---|---|---|
| (1, 2) | (1, 2) | min(|1 − 2|, |1 + 2|) = 1 |
1 | max(|1 − 2|, |1 + 2|) = 3 |
2 |
| (2, 3) | (2, 3) | min(|2 − 3|, |2 + 3|) = 1 |
2 | max(|2 − 3|, |2 + 3|) = 5 |
3 |
Example 2:
Input: nums = [-3,2,-1,4]
Output: 4
Explanation:
There are 4 perfect pairs:
(i, j) |
(a, b) |
min(|a − b|, |a + b|) |
min(|a|, |b|) |
max(|a − b|, |a + b|) |
max(|a|, |b|) |
|---|---|---|---|---|---|
| (0, 1) | (-3, 2) | min(|-3 - 2|, |-3 + 2|) = 1 |
2 | max(|-3 - 2|, |-3 + 2|) = 5 |
3 |
| (0, 3) | (-3, 4) | min(|-3 - 4|, |-3 + 4|) = 1 |
3 | max(|-3 - 4|, |-3 + 4|) = 7 |
4 |
| (1, 2) | (2, -1) | min(|2 - (-1)|, |2 + (-1)|) = 1 |
1 | max(|2 - (-1)|, |2 + (-1)|) = 3 |
2 |
| (1, 3) | (2, 4) | min(|2 - 4|, |2 + 4|) = 2 |
2 | max(|2 - 4|, |2 + 4|) = 6 |
4 |
Example 3:
Input: nums = [1,10,100,1000]
Output: 0
Explanation:
There are no perfect pairs. Thus, the answer is 0.
Constraints:
2 <= nums.length <= 105-109 <= nums[i] <= 109
Approach Overview
Problem Overview: You receive an integer array and must count pairs (i, j) where i < j and the two numbers form a perfect pair based on relationships between their absolute values and sums/differences. The trick is recognizing that the condition simplifies when you work with absolute values.
Approach 1: Brute Force Pair Checking (O(n^2) time, O(1) space)
Check every pair (i, j) and directly evaluate the perfect pair conditions using |x - y|, |x + y|, and the absolute values of the numbers. This approach uses two nested loops over the array. While straightforward, it performs roughly n*(n-1)/2 comparisons, which becomes slow for large inputs. It is still useful for validating edge cases or confirming the correctness of an optimized approach.
Approach 2: Sort + Two Pointers (O(n log n) time, O(1) space)
The key insight: the pair condition depends only on absolute values. Convert each number to |nums[i]|, then sort the array using sorting. For two values a ≤ b, the perfect pair constraints reduce to checking whether b ≤ 2 * a. Once sorted, maintain two pointers. Fix the left pointer l and expand the right pointer r while nums[r] ≤ 2 * nums[l]. Every valid range contributes r - l - 1 pairs. This sliding window style scan avoids recomputing comparisons and efficiently counts all valid pairs.
This pattern is a common interview trick: convert the condition into a monotonic relationship after sorting, then apply the two pointers technique to scan the array in linear time.
Recommended for interviews: Start by explaining the brute force approach to demonstrate understanding of the pair condition. Then transition to the sorted absolute value insight and apply two pointers. Interviewers typically expect the O(n log n) solution with sorting plus a linear scan because it shows you can simplify mathematical constraints and apply efficient pointer techniques.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n^2) | O(1) | Small inputs or validating the correctness of optimized logic |
| Sort + Two Pointers | O(n log n) | O(1) | Optimal approach for interviews and large arrays |
| Sort + Binary Search | O(n log n) | O(1) | Alternative after sorting when using binary search to find the valid range for each element |