2563. Count-The-Number-Of-Fair-Pairs

This one was difficult… The trick was to see that we can count the number of valid pairs that have a sum of at most x where x is either upper or lower - 1.

Instead of tracking if the sum is between lower and upper for a pair, if we only have one of the limits to compare to, we can solve it using a 2 pointer approach if we sort the array at the start.

class Solution(object):
    def countFairPairs(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        nums.sort()

        return self.countAtMost(nums, upper) - self.countAtMost(nums, lower - 1)

    def countAtMost(self, nums, comp):
        ans = 0
        j = len(nums) - 1
        for i in range(len(nums)):
            while i < j and nums[i] + nums[j] > comp:
                j -= 1
            if i < j:
                ans += j - i
        return ans

Time Complexity: O(n log n)

Space Complexity: O(n)

Time Taken: 44m 19s