Count the Number of Fair Pairs — Problem & Solution
Count the Number of Fair Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Count the Number of Fair Pairs is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search, Two Pointers
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums of length n and two integers lower and upper, count the fair pairs.
A pair of indices (i, j) is fair when 0 <= i < j < n and lower <= nums[i] + nums[j] <= upper.
CodeKairo note: the original allows n up to 10^5 and returns a 64-bit count; here n <= 5 * 10^4, so the answer fits in a 32-bit integer. A single pair sum can still reach 2 * 10^9.
Example 1
Input: nums = [2,-1,5,3,0], lower = 2, upper = 5
Output: 6
Explanation: The pairs with sums 5 (2+3), 2 (2+0), 4 (-1+5), 2 (-1+3), 5 (5+0) and 3 (3+0).
Example 2
Input: nums = [4,6,1,9], lower = 10, upper = 10
Output: 2
Explanation: 4 + 6 and 1 + 9.
Example 3
Input: nums = [7], lower = 0, upper = 100
Output: 0
Explanation: A single element forms no pair.
Constraints
1 <= nums.length <= 5 * 10^4-10^9 <= nums[i] <= 10^9-10^9 <= lower <= upper <= 10^9
Hints for Count the Number of Fair Pairs
Hint 1
The count of pairs does not depend on the order of the array — only on which values exist. So you may sort it.
Hint 2
Counting pairs with a sum inside
[lower, upper]is (pairs with sum<= upper) minus (pairs with sum<= lower - 1).Hint 3
In a sorted array, count pairs with sum
<= xwith two pointers: ifa[i] + a[j] <= x, all ofa[i+1..j]pair witha[i], so addj - iand moveiright; otherwise movejleft.
How to solve Count the Number of Fair Pairs
Sorting does not change the set of unordered pairs, and on a sorted array "how many pairs sum to at most x" is a linear two-pointer count. The range answer is the difference of two such counts.
Approach
- Sort a copy of
numsascending. - Define
atMost(x): withi = 0,j = n - 1, whilei < j: ifa[i] + a[j] <= x, addj - i(every partner ofa[i]ini+1..j) and incrementi; otherwise decrementj. - Return
atMost(upper) - atMost(lower - 1).
Why it works
If a[i] + a[j] <= x, then a[i] + a[t] <= x for every t in (i, j] because the array is sorted, so all j - i pairs are counted at once and a[i] is finished. If the sum is too big, a[j] exceeds the limit with every remaining partner (all of them are >= a[i]), so a[j] is finished. Each step finishes one element, so each pair is classified exactly once.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- Pair sums reach ±2·10^9, beyond 32-bit range — add in 64-bit.
- Count unordered pairs
i < j: never pair an element with itself. - Binary search per element (lower/upper bound in the suffix) also works in O(n log n); the two-pointer version avoids off-by-one errors with the bounds.
Reference solution
Python
from typing import List
def countFairPairs(nums: List[int], lower: int, upper: int) -> int:
a = sorted(nums)
def at_most(limit: int) -> int:
i = 0
j = len(a) - 1
cnt = 0
while i < j:
if a[i] + a[j] <= limit:
cnt += j - i
i += 1
else:
j -= 1
return cnt
return at_most(upper) - at_most(lower - 1)Java
static long fairAtMost2563(int[] a, long limit) {
int i = 0, j = a.length - 1;
long cnt = 0;
while (i < j) {
if ((long) a[i] + a[j] <= limit) { cnt += j - i; i++; }
else j--;
}
return cnt;
}
public static int countFairPairs(int[] nums, int lower, int upper) {
int[] a = nums.clone();
Arrays.sort(a);
return (int) (fairAtMost2563(a, upper) - fairAtMost2563(a, (long) lower - 1));
}C++
long long fairAtMost2563(const vector<int>& a, long long limit) {
int i = 0, j = (int) a.size() - 1;
long long cnt = 0;
while (i < j) {
if ((long long) a[i] + a[j] <= limit) { cnt += j - i; i++; }
else j--;
}
return cnt;
}
int countFairPairs(vector<int>& nums, int lower, int upper) {
vector<int> a(nums.begin(), nums.end());
sort(a.begin(), a.end());
return (int) (fairAtMost2563(a, upper) - fairAtMost2563(a, (long long) lower - 1));
}JavaScript
var countFairPairs = function(nums, lower, upper) {
var a = nums.slice().sort(function(x, y) { return x - y; });
var atMost = function(limit) {
var i = 0, j = a.length - 1, cnt = 0;
while (i < j) {
if (a[i] + a[j] <= limit) { cnt += j - i; i++; }
else j--;
}
return cnt;
};
return atMost(upper) - atMost(lower - 1);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms