aboutsummaryrefslogtreecommitdiff
path: root/count_num_fair_pairs.py
blob: 5933dbda6cb0a35c7e31e99d5e6a19d848d2bcad (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 2563. Count the Number of Fair Pairs
import bisect

"""
given a 0 indexed integer array 'nums' of size 'n', and two integers 'lower'
and 'upper', return the number of fair pairs. pair '(i, j)' is fair is '0 <=
i < j < n' and 'lower <= nums[i] + nums[j] <= upper'
"""


class Solution(object):
    def countFairPairs(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        nums.sort()
        ans = 0
        for i in range(len(nums) - 1, -1, -1):
            v = nums[i]
            a = bisect.bisect_left(nums, lower - v, lo=0, hi=i)
            b = bisect.bisect_right(nums, upper - v, lo=0, hi=i)
            ans += b - a
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(obj.countFairPairs(nums=[0, 1, 7, 4, 4, 5], lower=3, upper=6))
    print(obj.countFairPairs(nums=[1, 7, 9, 2, 5], lower=11, upper=11))