Problem of The Day: Count the number of fair pairs

Problem Statement

leetcode problem link

Intuition

To solve this problem efficiently, we want to avoid checking all pairs directly, which would result in O(n²) time. Instead, we consider sorting the array and using a two-pointer technique to count the number of valid pairs within the given sum range. This approach is both elegant and efficient.

Approach

1. Sort the input array nums to enable efficient range-based sum counting using the two-pointer technique.
2. Define a helper function helper(target) that counts the number of index pairs (i, j) where nums[i] + nums[j] < target.
   • Use two pointers l and r to scan the array from both ends.
   • If the sum of nums[l] + nums[r] is less than target, all elements between l and r can form a valid pair with nums[l]. Increment the count accordingly and move l forward.
   • Otherwise, move r backward to find a smaller pair.
3. Use the helper function to calculate:
   • helper(upper + 1) → counts pairs with sum ≤ upper
   • helper(lower) → counts pairs with sum < lower
   • The result is the difference: helper(upper + 1) - helper(lower), which gives the number of pairs with sum in [lower, upper].

Complexity

• Time complexity:
  \(O(n \log n)\)
  Sorting takes ( O(n \log n) ) and each helper call takes ( O(n) ). Since we call the helper twice, total time is still ( O(n \log n) ).

• Space complexity:
  \(O(1)\)
  Aside from sorting (which may require some space depending on the implementation), no extra space is used.

Code

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

        def helper(target):
            l, r = 0, N - 1
            ans = 0
            while l < r:
                val = nums[l] + nums[r]
                if val < target:
                    ans += r - l
                    l += 1
                else:
                    r -= 1
            return ans

        return helper(upper + 1) - helper(lower)