Skip to main content
Talentd

Number of Perfect Pairs - Solution & Explanation

MediumArrayMathTwo PointersSorting4 min readAsked at: Goldman Sachs, Visa, Atlassian +3
Practice this problem

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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n^2)O(1)Small inputs or validating the correctness of optimized logic
Sort + Two PointersO(n log n)O(1)Optimal approach for interviews and large arrays
Sort + Binary SearchO(n log n)O(1)Alternative after sorting when using binary search to find the valid range for each element

Video Solution

Number of Perfect Pairs | Leetcode 3649 | Q2 - Biweekly Contest 163 • ExpertFunda • 1,092 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Number of Perfect Pairs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays