3649. Number of Perfect Pairs
Asked at Atlassian
Difficulty
Medium
Time
O(n log n)
Space
O(1) extra (ignoring the sort)
Pattern
Array
Companies
1
Problem
You get an integer array nums. A pair of indices (i, j) is called perfect when i < j and the two values a = nums[i], b = nums[j] satisfy two rules:
min(|a - b|, |a + b|) <= min(|a|, |b|)max(|a - b|, |a + b|) >= max(|a|, |b|)
Here |x| means the absolute value of x (drop the minus sign). Count how many perfect pairs exist and return that count.
The two rules look scary, but they collapse into one simple test. If you sort the values so that a <= b, the pair is perfect exactly when b <= 2 * a. So the real job is: sort the array, then count pairs where the larger value is at most twice the smaller value. Note that pairs are counted by index, so equal values at different positions count as separate pairs.
Which pairs are perfect?
Constraints
- ●
2 <= nums.length <= 10^5 - ●
-10^9 <= nums[i] <= 10^9
Examples
nums = [0,1,2,3]2nums = [-3,2,-1,4]4nums = [1,10,100,1000]0Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Medium | View all Atlassian questions → |
How to Think About It
Brute force: check every pair (i, j) with i < j and test the condition — O(n²) time.
Rearrange the condition: for sorted array with a[i] <= a[j], the condition becomes a[j] - a[i] <= a[i], i.e., a[j] <= 2 * a[i].
Sort the array and for each element a[i], use binary search or two pointers to find the farthest a[j] such that a[j] <= 2 * a[i].
Two pointers: maintain a right pointer that advances as a[i] increases, since 2 * a[i] only grows.
Optimal: sort and use two pointers in O(n log n) time for sorting plus O(n) for the two-pointer scan.
Optimal Approach
Sort the array. For sorted a where a[i] <= a[j], the condition |a[i] - a[j]| <= min(a[i], a[j]) simplifies to a[j] <= 2 * a[i]. Use two pointers: for each left index i, advance the right pointer j as far as possible while a[j] <= 2 * a[i]. All pairs (i, i+1), (i, i+2), ..., (i, j) are valid. Add j - i to the result. This runs in O(n log n) for sorting and O(n) for the two-pointer scan.
Two pointers after sorting
What Trips People Up in Real Interviews
Clarify whether the condition uses absolute value and whether negative numbers are possible.
Derive the simplified condition a[j] <= 2 * a[i] for sorted arrays — this is the key insight.
Make sure to count pairs where i < j only (avoid double counting).
Ask about integer overflow when computing 2 * a[i] — use long if needed.
Discuss why sorting preserves correctness: if the condition holds for sorted indices, it holds for the original pairs.
Solution Code
O(n log n) timedef countPerfectPairs(nums):
nums.sort()
n = len(nums)
result = 0
j = 0
for i in range(n):
while j < n and nums[j] <= 2 * nums[i]:
j += 1
result += j - i - 1
return resultFrequently Asked Questions
What is the Number of Perfect Pairs problem?
Given an integer array nums, a pair (i, j) is called perfect if i < j and |nums[i] - nums[j]| <= min(nums[i], nums[j]). Return the total number of perfect pairs in the array.
How do you solve Number of Perfect Pairs?
The optimal approach runs in O(n log n) time and O(1) extra (ignoring the sort) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Number of Perfect Pairs?
Number of Perfect Pairs is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Number of Perfect Pairs?
- Clarify whether the condition uses absolute value and whether negative numbers are possible.
- Derive the simplified condition a[j] <= 2 * a[i] for sorted arrays — this is the key insight.
- Make sure to count pairs where i < j only (avoid double counting).
- Ask about integer overflow when computing 2 * a[i] — use long if needed.
- Discuss why sorting preserves correctness: if the condition holds for sorted indices, it holds for the original pairs.