Count the Number of Fair Pairs

main.md

Question

Approach

Implementation

from bisect import bisect_left, bisect_right

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

        for i in range(n):
            left = bisect_left(nums, lower - nums[i], i + 1, n)
            right = bisect_right(nums, upper - nums[i], i + 1, n)
            count += right - left

        return count

Complexities

• Time: O(n logn)
• Space: O(1)