Count the Number of Fair Pairs

Leetcode Problem:

• Count the Number of Fair Pairs

Summary

• The problem is to count the number of fair pairs in a given array of integers within a specified range.

Approach

• The solution uses a two-pointer technique to find the range of possible values for each pair, and then calculates the number of fair pairs by summing up the counts of pairs that fall within the specified range.

Complexity

• O(n log n + n log n) = O(n log n)

Explanation

• The solution first sorts the input array
• Then, for each element in the array, it uses two pointers (low and up) to find the range of possible values for the other element in the pair
• The low pointer is used to find the smallest possible value for the other element, and the up pointer is used to find the largest possible value
• The solution then calculates the number of fair pairs by summing up the counts of pairs that fall within the specified range.

Solution Code:

class Solution {
public:
    long long countFairPairs(vector& nums, int lower, int upper) {
        sort(nums.begin(), nums.end());
        
        long long ans = 0;
        for(int i = 0 ; i < nums.size(); i++){
            int l = i+1;
            int r = nums.size() - 1;
            int low = 123456789;
            while(l <= r){
                int mid = (l + r ) / 2;
                if(nums[mid] + nums[i] >= lower){
                    r = mid - 1;
                    low = mid;
                }else{
                    l = mid + 1;
                }
            }
            l = i + 1;
            r = nums.size() - 1;
            int up = 0;
            while(l <= r){
                int mid = (l + r ) / 2;
                if(nums[mid] + nums[i] <= upper){
                    l = mid + 1;
                    up = mid;
                }else{
                    r = mid - 1;
                }
            }
            if(low<=up){
                ans += up - low + 1;
            }
        }
        return ans;
    }
};