Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Count pairs with sum below a threshold, then subtract the count below lower from the count below upper + 1. Sorting enables a two-pointer count: if the smallest and largest remaining values fit, the smallest also fits with every position between them.

Approach

Sort the values. In the threshold helper, when the endpoint sum is below the target, add right - left pairs and advance left. Otherwise decrease right, since that largest value cannot pair with any remaining value under the threshold. Stop when the pointers meet. Return the difference of the two helper counts. Sorting preserves pair multiplicity, including duplicates, and the upper + 1 threshold makes the upper bound inclusive.

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()

        def tw(target):
            l = 0
            h = len(nums) - 1
            count = 0

            while l < h:
                sum = nums[l] + nums[h]
                if sum < target:
                    count += h - l
                    l += 1
                else:
                    h -= 1

            return count
        
        return tw(upper + 1) - tw(lower)

Complexity analysis

Let n = nums.length. Time: O(n log n) for sorting plus two linear two-pointer counts. Auxiliary space: up to O(n) for sorting workspace.