Count the Number of Fair Pairs

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;
    }
};

To solve the problem of counting the number of fair pairs within a specified value range in an array, the following C++ solution employs a two-pointer technique after sorting the initial data array.

• First, sort the data array to orderly enhance the efficiency of the pair finding process.
• Calculate the number of pairs where the sum of elements is at least minVal but less than maxVal + 1 using the calculateLowerBound function.

The calculateLowerBound function operates by:

1. Initializing two pointers, start and end, at the beginning and the end of the array respectively.
2. Looping through the array with these pointers to find and count pairs that meet the condition where their sum is less than the target.
3. If the sum of the elements pointed by start and end is less than the target:
   • Increment the count by the difference between end and start, as each element between these pointers with the start element can form a valid pair.
   • Move the start pointer one position forward.
4. If the condition is not met, simply move the end pointer one position backward.
5. Finally, return the count of such pairs which is accumulated in the variable count.

This solution efficiently calculates the difference between the valid pair counts corresponding to the upper and lower bounds of the sum, thus obtaining the count of fair pairs that lie within the given range.

class Solution {

    public long calculateFairPairs(int[] array, int minRange, int maxRange) {
        Arrays.sort(array);
        return find_lower_bound(array, maxRange + 1) - find_lower_bound(array, minRange);
    }

    // Search for pairs whose combined sum is less than the specified `value`.
    private long find_lower_bound(int[] array, int target) {
        int start = 0, end = array.length - 1;
        long count = 0;
        while (start < end) {
            int total = array[start] + array[end];
            if (total < target) {
                count += (end - start);
                start++;
            } else {
                end--;
            }
        }

        return count;
    }
}

The solution presented here counts the number of "fair pairs" in an array where the sum of each pair falls within a specified inclusive range. The Java-based method calculateFairPairs takes an integer array and two integers defining the minimum and maximum range.

Here's a step-by-step breakdown of how the solution works:

1. Sort the input array to order the elements, which facilitates pair checking based on their sum.
2. Use two helper searches to define the boundaries of sums within the given range via find_lower_bound. This function is called twice to:
   • Find the count of pairs with sums less than or equal to maxRange.
   • Subtract from it the count of pairs with sums less than minRange.
3. The helper method find_lower_bound utilizes a two-pointer approach to efficiently count pairs with sums less than a target value:
   • Initialize two pointers, one at the start and the other at the end of the array.
   • Traverse the array using these pointers by:
     • Calculating the sum of elements at pointers' positions.
     • If the sum is below the target, increment the count by the number of elements between the pointers and move the start pointer.
     • If the sum equals or exceeds the target, move the end pointer backwards.
4. Return the computed difference between the two searches as the total count of fair pairs.

This logic ensures an efficient computation by limiting the number of operations, leveraging sorted array properties along with the two-pointer technique.

class Solution:
    def countValidPairs(self, arr: List[int], min_value: int, max_value: int) -> int:
        arr.sort()
        return self.upper_bound(arr, max_value + 1) - self.upper_bound(arr, min_value)

    def upper_bound(self, numbers: List[int], target: int) -> int:
        start = 0
        end = len(numbers) - 1
        count = 0
        while start < end:
            current_sum = numbers[start] + numbers[end]
            if current_sum < target:
                count += end - start
                start += 1
            else:
                end -= 1
        return count

The provided Python script offers a solution to determine the count of fair pairs in an array, where the sum of each pair falls between a specified minimum and maximum value, inclusive. The script consists of a class Solution with two methods:

• countValidPairs(arr, min_value, max_value): This method initiates the process by sorting the array and then calculates the number of valid pairs. It achieves this by subtracting the number of pairs with sums below the min_value from those below max_value + 1, utilizing the upper_bound method for these calculations.

• upper_bound(numbers, target): This auxiliary method assists by finding how many pairs of numbers from a sorted list have sums less than a given target. It uses a two-pointer technique to efficiently compute the count.

This approach ensures that all pairs are tested for their sum against the min_value and max_value without explicitly iterating through each possible pair, rather leveraging sorted properties and two-pointer scan for optimization. This method significantly enhances the performance for large datasets by maintaining a time complexity approximately in the order of O(n log n) due to the initial sort and a subsequent linear scan.