Count the Number of Fair Pairs

Problem Statement

Given a 0-indexed integer array called nums with size n, accompanied by two integer values, lower and upper, the task is to determine the number of "fair pairs" in the array. A pair (i, j) is labeled as fair if it satisfies both of the following conditions:

1. The indices i and j are such that 0 <= i < j < n, meaning i is less than j and both indices are within array bounds.
2. The sum of the elements at these indices falls within the inclusive range [lower, upper] (i.e., lower <= nums[i] + nums[j] <= upper).

This problem involves checking combinations of elements in the array to see how many such combinations fit within the specified sum range.

Examples

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 <= 105
• nums.length == n
• -109 <= nums[i] <= 109
• -109 <= lower <= upper <= 109

Approach and Intuition

The problem essentially requires us to count how many pairs of elements in the array sum to a value within a specified range. Here's a simplified breakdown of our approach:

1. Iterate over each element nums[i] where i ranges from 0 to n-1.
2. For each i, iterate over subsequent elements nums[j] where j ranges from i+1 to n-1.
3. For each pair (i, j), compute the sum nums[i] + nums[j].
4. Check if this sum falls within the given bounds, [lower, upper].
5. If the condition is satisfied, increment our count of fair pairs.

Given the constraints, this naive approach might not be efficient enough, especially for large arrays (up to 100,000 elements). This could potentially lead to roughly 5 billion comparisons in the worst-case scenario. To optimize:

• Take advantage of sorting or other algorithms, like binary search, to select elements within required range quickly. However, care must be taken to handle indices correctly when elements are moved (sorting).
• Utilize data structures like segment trees or binary indexed trees to count sums efficiently, though this requires elevated knowledge of such structures and potentially complex implementation.
• Utilize two-pointer technique after sorting to find pairs within bounds, a classic approach in problems involving ranges or pairs that sum to a specific target.

While this overview provides a strategy to tackle the problem, the efficiency and feasibility of each method could vary based on actual data size and specific values of lower and upper.

Solutions

class Solution {
public:
    long long countFairPairs(vector<int>& data, int minVal, int maxVal) {
        sort(data.begin(), data.end());
        return calculateLowerBound(data, maxVal + 1) - calculateLowerBound(data, minVal);
    }
    
private:
    long long calculateLowerBound(vector<int>& data, int target) {
        int start = 0, end = data.size() - 1;
        long long count = 0;
        while (start < end) {
            int sum = data[start] + data[end];
            if (sum < target) {
                count += (end - start);
                start++;
            } else {
                end--;
            }
        }
        return count;
    }
};