Number of Perfect Pairs
Asked at Atlassian
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.
Asked At
| 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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.