Problem Informations

• Problem Index: 2563
• Problem Link: Count the Number of Fair Pairs
• Topics: Array, Two Pointers, Binary Search, Sorting

Problem Description

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 \leq i < j < n$, and
• $lower \leq nums[i] + nums[j] \leq 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 \leq nums.length \leq 10^5$
• $nums.length == n$
• $-10^9 \leq nums[i] \leq 10^9$
• $-10^9 \leq lower \leq upper \leq 10^9$

Intuition

The problem asks us to determine how many pairs of indices in the array satisfy a certain condition on their summed values. A straightforward approach would be to use two nested loops to sum all pairs and check which sums fall within the specified bounds. However, this naive approach would be inefficient for large arrays due to its $\mathcal{O}(n^2)$ complexity. Thus, a more efficient method involves sorting the array and exploiting binary search to significantly reduce the number of comparisons needed to count fair pairs.

Approach

The solution leverages a sorted array to efficiently count pairs of indices whose sums fall within a specified range. The steps are as follows:

1. Initialization: Start with an empty list, previousNumbers, to keep track of numbers processed so far in sorted order, and a counter, fairPairCount, initialized to zero.

2. Iterate through the array: For each element num in the given array nums:

   • Binary Search for Range: Use binary search to determine the range of numbers in previousNumbers that can form a fair pair with num. Specifically, use:

     • lower_bound to find the first element in previousNumbers that, when added to num, results in a sum not less than lower.
     • upper_bound to find the first element in previousNumbers that, when added to num, results in a sum greater than upper.

   • Count Valid Indices: The difference between the upper_bound and lower_bound iterators gives the number of valid indices in previousNumbers that satisfy the condition.

3. Insert and Maintain Order: Insert the current num into previousNumbers in a position that maintains the list’s sorted order. This step ensures previousNumbers is ready for the next iteration.

4. Return Count: After processing all elements, fairPairCount will contain the total number of fair pairs.

By maintaining a sorted list of previously processed numbers and using binary search to efficiently find bounds within this list, we reduce the problem of counting fair pairs to a task manageable in $\mathcal{O}(n \log n)$ time complexity. This significant reduction is achieved by combining sorting, binary search, and clever use of data structures, which together provide a scalable solution to the problem.

Code

C++

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        vector<int> previousNumbers;
        long long fairPairCount = 0;

        for (int num : nums) {
            // Find the lower bound: first element not less than (lower - num)
            vector<int>::iterator lowerBoundIt = lower_bound(previousNumbers.begin(), previousNumbers.end(), lower - num);

            // Find the upper bound: first element greater than (upper - num)
            vector<int>::iterator upperBoundIt = upper_bound(previousNumbers.begin(), previousNumbers.end(), upper - num);

            // Calculate the number of elements in the range [lower - num, upper - num]
            fairPairCount += upperBoundIt - lowerBoundIt;

            // Insert 'num' in the sorted position within 'previousNumbers'
            previousNumbers.insert(upper_bound(previousNumbers.begin(), previousNumbers.end(), num), num);
        }

        return fairPairCount;
    }
};

Python

class Solution:
    def countFairPairs(self, nums, lower, upper):
        previousNumbers = []
        fairPairCount = 0

        for num in nums:
            # Find the lower bound: first element not less than (lower - num)
            lowerBoundIt = self.lower_bound(previousNumbers, lower - num)

            # Find the upper bound: first element greater than (upper - num)
            upperBoundIt = self.upper_bound(previousNumbers, upper - num)

            # Calculate the number of elements in the range [lower - num, upper - num]
            fairPairCount += upperBoundIt - lowerBoundIt

            # Insert 'num' in the sorted position within 'previousNumbers'
            previousNumbers.insert(self.upper_bound(previousNumbers, num), num)

        return fairPairCount

    def lower_bound(self, nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        return left

    def upper_bound(self, nums, target):
        left, right = 0, len(nums)
        while left < right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return left

Complexity

• Time complexity: The time complexity is $O(n \log n)$. This is because for each element in the input vector nums, we perform a lower_bound and upper_bound operation on the vector previousNumbers, both of which take $O(\log n)$ time in the worst case since the vector is maintained in sorted order. Additionally, inserting an element into the sorted vector previousNumbers using upper_bound also takes $O(\log n)$ time. Since there are $n$ elements in nums, the overall time complexity is $O(n \log n)$.

• Space complexity: The space complexity is $O(n)$. This is because we use an auxiliary vector previousNumbers to store the numbers seen so far in sorted order, which in the worst case can contain up to all $n$ elements from the input vector nums. Therefore, the space complexity is $O(n)$.