Count the Number of Fair Pairs
MedPrompt
Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.
A pair (i, j) is fair if:
0 <= i < j < n, andlower <= nums[i] + nums[j] <= upper
Example 1:
Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6
Output: 6
Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).Example 2:
Input: nums = [1,7,9,2,5], lower = 11, upper = 11
Output: 1
Explanation: There is a single fair pair: (2,3).
Constraints:
1 <= nums.length <= 105nums.length == n-109 <= nums[i] <= 109-109 <= lower <= upper <= 109
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves checking every possible pair of indices (i, j) where i < j. For each pair, we calculate the sum of the corresponding elements and check if it falls within the given [lower, upper] range.
Algorithm
- Initialize a counter
countto 0. - Use a nested loop. The outer loop iterates
ifrom0ton-2. - The inner loop iterates
jfromi+1ton-1. - Inside the inner loop, calculate
sum = nums[i] + nums[j]. - Check if
lower <= sum <= upper. - If the condition is true, increment
count. - After the loops complete, return
count.
Walkthrough
The brute-force method is the most straightforward way to solve the problem. We iterate through all possible unique pairs of elements in the array, calculate their sum, and check if the sum is 'fair'.
- We initialize a counter for fair pairs to zero.
- We use two nested loops to generate all unique pairs
(i, j)withi < j. The outer loop runs fromi = 0ton-2, and the inner loop runs fromj = i+1ton-1. - Inside the inner loop, we compute the sum
(long) nums[i] + nums[j]to avoid potential integer overflow. - We then check if
lower <= sum <= upper. - If the condition is met, we increment our counter.
- After iterating through all pairs, the counter holds the total number of fair pairs.
class Solution { public long countFairPairs(int[] nums, int lower, int upper) { long count = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { long sum = (long) nums[i] + nums[j]; if (sum >= lower && sum <= upper) { count++; } } } return count; }}Complexity
Time
O(n^2), where n is the number of elements in `nums`. We iterate through all possible pairs, which is n * (n-1) / 2.
Space
O(1) extra space, as we only use a few variables to store the count and loop indices.
Trade-offs
Pros
Simple to understand and implement.
Requires no modification of the input array.
Cons
Highly inefficient for large input sizes.
Will cause a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
A more efficient approach is to first sort the array. Then, for each element nums[i], we can use binary search to find how many other elements nums[j] (with j > i) satisfy the condition lower <= nums[i] + nums[j] <= upper. This condition can be rewritten as lower - nums[i] <= nums[j] <= upper - nums[i].
Algorithm
- Sort the input array
nums. - Initialize a
countof fair pairs to 0. - Iterate through the array with an index
ifrom0ton-1. - For each
nums[i], determine the required range fornums[j]as[lower - nums[i], upper - nums[i]]. - Use binary search on the subarray
nums[i+1...n-1]to find the number of elementsnums[j]that fall into this range. - This can be done by finding the index of the first element
>= (lower - nums[i])(let's call itstart) and the index of the first element> (upper - nums[i])(let's call itend). - The number of valid
j's for the currentiisend - start. - Add this number to the total
count. - Return
countafter the loop finishes.
Walkthrough
By sorting the array, we can leverage binary search to speed up the process of finding valid partners for each element. For each nums[i], we are looking for nums[j] in the remainder of the sorted array.
- First, we sort the input array
nums. - We iterate through the array with an index
i. - For each
nums[i], we definemin_val = lower - nums[i]andmax_val = upper - nums[i]. - We then need to count elements in
numsfrom indexi+1ton-1that are in the range[min_val, max_val]. - We can find this count by performing two binary searches:
- Find the index of the first element
>= min_val(the lower bound). - Find the index of the first element
> max_val(the upper bound).
- Find the index of the first element
- The difference between these two indices gives the number of valid
j's for the currenti. - We sum these counts for all
ito get the total.
import java.util.Arrays; class Solution { public long countFairPairs(int[] nums, int lower, int upper) { Arrays.sort(nums); long count = 0; int n = nums.length; for (int i = 0; i < n; i++) { int start = findLowerBound(nums, i + 1, (long) lower - nums[i]); int end = findUpperBound(nums, i + 1, (long) upper - nums[i]); count += (end - start); } return count; } // Finds the first index `j` in nums[left...] such that nums[j] >= target private int findLowerBound(int[] nums, int left, long target) { int right = nums.length - 1; int result = nums.length; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { result = mid; right = mid - 1; } else { left = mid + 1; } } return result; } // Finds the first index `j` in nums[left...] such that nums[j] > target private int findUpperBound(int[] nums, int left, long target) { int right = nums.length - 1; int result = nums.length; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] > target) { result = mid; right = mid - 1; } else { left = mid + 1; } } return result; }}Complexity
Time
O(n log n). Sorting takes O(n log n). The main loop runs `n` times, and each iteration performs two binary searches, each taking O(log n). The total time is O(n log n + n * log n) = O(n log n).
Space
O(log n) or O(n), depending on the space complexity of the sorting algorithm used. Java's `Arrays.sort` for primitives has an average space complexity of O(log n).
Trade-offs
Pros
Significantly more efficient than brute force.
Guaranteed to pass within the time limits for the given constraints.
Cons
More complex to implement than brute force.
Modifies the input array by sorting it. A copy must be made if the original order is needed.
While efficient, it's slightly slower than the two-pointer approach due to repeated binary searches.
This is the most optimal approach. The core idea is to reframe the problem. Instead of directly counting pairs in the range [lower, upper], we can calculate the number of pairs whose sum is less than or equal to a certain value K. The number of fair pairs is then (pairs with sum <= upper) - (pairs with sum <= lower - 1). This subproblem can be solved efficiently in linear time on a sorted array using a two-pointer technique.
Algorithm
- Define a helper function
countLessEqual(K)that counts pairs(i, j)withi < jandnums[i] + nums[j] <= K. - Inside
countLessEqual(K): a. Use two pointers,left = 0andright = n-1. b. Whileleft < right: i. Ifnums[left] + nums[right] <= K, it meansnums[left]can form a valid pair withnums[left+1], ..., nums[right]. Addright - leftto the count and incrementleft. ii. Otherwise, the sum is too large, so decrementright. c. Return the total count. - In the main function, first sort the
numsarray. - The final result is
countLessEqual(upper) - countLessEqual(lower - 1).
Walkthrough
This approach refines the sorting idea by using a more efficient two-pointer technique instead of repeated binary searches. The key insight is that the number of pairs (i, j) satisfying lower <= sum <= upper is equal to (number of pairs with sum <= upper) - (number of pairs with sum < lower).
We can write a helper function countLessEqual(K) that efficiently counts pairs with a sum less than or equal to K on a sorted array.
countLessEqual(K)function:- Initialize two pointers,
leftat the start of the array andrightat the end. - While
left < right:- If
nums[left] + nums[right] <= K, we have found a valid pair. Since the array is sorted,nums[left]can also be paired with any element betweenleft+1andright, and the sum will also be<= K. There areright - leftsuch pairs. We add this to our count and moveleftone step to the right to consider the next element. - If
nums[left] + nums[right] > K, the sum is too large. To reduce the sum, we must move therightpointer one step to the left.
- If
- Initialize two pointers,
- Main Logic:
- First, sort the
numsarray. - The total number of fair pairs is
countLessEqual(upper) - countLessEqual(lower - 1).
- First, sort the
import java.util.Arrays; class Solution { public long countFairPairs(int[] nums, int lower, int upper) { Arrays.sort(nums); return countLessEqual(nums, upper) - countLessEqual(nums, lower - 1); } private long countLessEqual(int[] nums, int val) { long count = 0; int left = 0; int right = nums.length - 1; while (left < right) { if ((long) nums[left] + nums[right] <= val) { // If nums[left] + nums[right] <= val, then for this left pointer, // all pairs (left, j) where left < j <= right are valid. // There are (right - left) such pairs. count += (right - left); left++; } else { // Sum is too large, need to decrease it by moving the right pointer. right--; } } return count; }}Complexity
Time
O(n log n). Sorting the array takes O(n log n). Each call to the `countLessEqual` helper function takes O(n) time because the two pointers traverse the array at most once. The total time complexity is dominated by the sort, resulting in O(n log n).
Space
O(log n) or O(n), depending on the space complexity of the sorting algorithm used. This is the same as the binary search approach.
Trade-offs
Pros
The most efficient solution.
The two-pointer scan is O(n), which is faster than the O(n log n) scan of the binary search approach.
The logic is clean and the helper function is reusable.
Cons
Requires sorting, which alters the input array.
The logic of breaking the problem into
count(<=upper) - count(<=lower-1)might be less intuitive at first.
Solutions
Solution
class Solution {public long countFairPairs(int[] nums, int lower, int upper) { Arrays.sort(nums); long ans = 0; int n = nums.length; for (int i = 0; i < n; ++i) { int j = search(nums, lower - nums[i], i + 1); int k = search(nums, upper - nums[i] + 1, i + 1); ans += k - j; } return ans; }private int search(int[] nums, int x, int left) { int right = nums.length; while (left < right) { int mid = (left + right) >> 1; if (nums[mid] >= x) { right = mid; } else { left = mid + 1; } } return left; }}class Solution {public: long long countFairPairs(vector<int> &nums, int lower, int upper) { long long ans = 0; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { auto j = lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]); auto k = lower_bound(nums.begin() + i + 1, nums.end(), upper - nums[i] + 1); ans += k - j; } return ans; }};class Solution: def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int: nums . sort() ans = 0 for i, x in enumerate(nums): j = bisect_left(nums, lower - x, lo=i + 1) k = bisect_left(nums, upper - x + 1, lo=i + 1) ans += k - j return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.