This problem exemplifies the difference between "searching for a value" and "counting a range."

The indices are a proxy for the count.

Sorting turns “which pairs are valid?” into “where is the cutoff index?”, and cutoff indices are countable without enumeration.

We're looking "above" the problem.

This is the inclusion-exclusion principle, or the prefix sum property.

Instead of trying to stay "inside" the narrow window of $[\text{lower}, \text{upper}]$, which is hard to manage with two pointers, we solve the "easier" problem: "How many pairs are less than X?"

Transform a hard condition (“sum in a range”) into something with a monotone boundary (“sum ≤ X”).

Then exploit that boundary to count in bulk.

Finally convert range back via subtraction.

https://gemini.google.com/app/fa4236fb21f99f13

https://chatgpt.com/g/g-68b11a82d24c81918000aa3a81424e5d-coach/c/6957fce7-f670-8326-b624-c02d219440f2

class Solution:
    def countFairPairs(self, nums, lower, upper):
        nums.sort()
        
        def countLessEqual(target):
            count = 0
            left = 0
            right = len(nums) - 1
            while left < right:
                if nums[left] + nums[right] <= target:
                    # All pairs between left and right work
                    count += (right - left)
                    left += 1
                else:
                    right -= 1
            return count
        
        return countLessEqual(upper) - countLessEqual(lower - 1)