Count the Number of Fair Pairs
Problem
Given a 0-indexed integer array nums and two integers lower and upper, count the number of fair pairs. A pair (i, j) is fair when 0 ≤ i < j < n and lower ≤ nums[i] + nums[j] ≤ upper.
nums = [0,1,7,4,4,5], lower = 3, upper = 66nums = [1,7,9,2,5], lower = 11, upper = 111def count_fair_pairs(nums, lower, upper):
nums.sort()
n = len(nums)
total = 0
for i in range(n):
# values nums[j], j > i, with sum in [lower, upper]
lo_t = lower - nums[i]
hi_t = upper - nums[i]
left = bisect_left(nums, lo_t, i + 1, n)
right = bisect_right(nums, hi_t, i + 1, n)
total += right - left
return totalfunction countFairPairs(nums, lower, upper) {
nums.sort((a, b) => a - b);
const n = nums.length;
let total = 0;
for (let i = 0; i < n; i++) {
// values nums[j], j > i, with sum in [lower, upper]
const loT = lower - nums[i];
const hiT = upper - nums[i];
const left = lowerBound(nums, loT, i + 1, n);
const right = upperBound(nums, hiT, i + 1, n);
total += right - left;
}
return total;
}long countFairPairs(int[] nums, int lower, int upper) {
Arrays.sort(nums);
int n = nums.length;
long total = 0;
for (int i = 0; i < n; i++) {
// values nums[j], j > i, with sum in [lower, upper]
long loT = lower - nums[i];
long hiT = upper - nums[i];
int left = lowerBound(nums, loT, i + 1, n);
int right = upperBound(nums, hiT, i + 1, n);
total += right - left;
}
return total;
}long long countFairPairs(vector<int>& nums, int lower, int upper) {
sort(nums.begin(), nums.end());
int n = nums.size();
long long total = 0;
for (int i = 0; i < n; i++) {
// values nums[j], j > i, with sum in [lower, upper]
long long loT = lower - nums[i];
long long hiT = upper - nums[i];
auto left = lower_bound(nums.begin() + i + 1, nums.end(), loT);
auto right = upper_bound(nums.begin() + i + 1, nums.end(), hiT);
total += right - left;
}
return total;
}Explanation
A fair pair only depends on the sum of two values, not on their original positions. Because of that, we are free to sort nums first — sorting never changes how many pairs sum into [lower, upper].
Fix an anchor index i. Every partner j > i must satisfy lower ≤ nums[i] + nums[j] ≤ upper. Subtracting nums[i] rewrites that as a window on the partner value itself: nums[j] must lie in [lower − nums[i], upper − nums[i]].
Since the suffix nums[i+1 .. n−1] is sorted, the partners that fall inside this window form one contiguous block. We find its edges with two binary searches: left = first index whose value is ≥ lower − nums[i] (lower bound), and right = first index whose value is > upper − nums[i] (upper bound).
The count of valid partners for this anchor is simply right − left. Adding that over all anchors gives the total number of fair pairs, with each pair counted once because we only ever look to the right of i.
Sorting costs O(n log n) and each of the n anchors does two O(log n) searches, so the whole algorithm is O(n log n) time and O(1) extra space (beyond the in-place sort).