Number of Perfect Pairs solution and explanation
8 more videos on this problem
Number of Perfect Pairs | Leetcode 3649 | Q2 - Biweekly Contest 163ExpertFunda · 10:36 · 1K views
Leetcode 3649 | Number of Perfect Pairs Detailed Explanation | Biweekly Contest 163 Q2Samrat Bhardwaj · 31:04 · 720 views
3649. Number of Perfect Pairs (Leetcode Medium)Programming Live with Larry · 28:12 · 504 views
3649. Number of Perfect Pairs | Leetcode Biweekly Contest 163Break and Build · 27:15 · 483 views
3649. Number of Perfect Pairs | Biweekly contest 163 | java solutioncodingX krishna · 26:02 · 306 views
Leetcode 3649 | Number of perfect pairs | Leetcode 3650 | Minimum Cost path with edge reversalsCodeWithMeGuys · 10:55 · 268 views
LeetCode 3649 | Number of Perfect PairsCode with Razan · 17:19 · 261 views
Number of Perfect Pairs | LeetCode 3649 (Medium) | Biweekly 163 | Greedy | C++codemintt · 16:10 · 151 views
LeetCode 3649 | Number of Perfect Pairs | C++ Solution Biweekly Contest Binary Search + MathsBEASTCODES · 22:15 · 123 views
The 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:
(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.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity 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 |
Frequently asked questions
Is Number of Perfect Pairs easy or hard?
Number of Perfect Pairs is typically rated Medium difficulty. The challenge is recognizing that the pair conditions simplify when you use absolute values and sorting. Once that insight is clear, the two pointers implementation is straightforward.
Number of Perfect Pairs Python/Java solution
Implement the optimal approach by converting numbers to absolute values, sorting the array, and scanning with two pointers. For each index l, expand r while nums[r] ≤ 2 * nums[l], then add r - l - 1 to the result. This works the same in Python, Java, C++, and Go.
How to solve Number of Perfect Pairs in O(n)?
Pure O(n) is generally not achievable because the problem requires ordering elements to apply the range condition. The typical optimal solution is O(n log n): convert numbers to absolute values, sort them, then use a two pointers sliding window to count pairs where nums[r] ≤ 2 * nums[l].
What is the best approach for Number of Perfect Pairs?
The most efficient approach sorts the absolute values of the array and uses a two pointers scan. After sorting, for values a ≤ b the perfect pair condition simplifies to checking whether b ≤ 2a. Expanding a right pointer for each left pointer counts valid ranges in linear time after sorting, giving O(n log n) time complexity.
Is Number of Perfect Pairs asked at Google/Amazon/Meta?
Problems combining math simplification with sorting and two pointers frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of pair counting with constraints on sums or absolute values are common interview patterns.
What data structure is used in Number of Perfect Pairs?
The solution mainly relies on arrays plus algorithmic techniques: sorting and the two pointers pattern. No advanced data structure is required because the pair condition becomes a simple range check after sorting the absolute values.
What is the time complexity of Number of Perfect Pairs?
The optimal solution runs in O(n log n) time due to sorting the array of absolute values. After sorting, a two pointers sweep processes the array in O(n) time. Space complexity remains O(1) if sorting is done in place.