LC-2563 Medium LeetCode

2563. Count the Number of Fair Pairs

Array Two Pointers Binary Search Sorting

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 53% Topics: Array, Two Pointers, Binary Search, Sorting

Reading material

Arrays & Hashing 12 min Two Pointers 9 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(1)

# sort, two pointers
class Solution(object):
    def countFairPairs(self, nums, lower, upper):
        """
        :type nums: List[int]
        :type lower: int
        :type upper: int
        :rtype: int
        """
        def count(x):
            cnt = 0
            left, right = 0, len(nums)-1
            while left < right:
                if nums[left]+nums[right] <= x:
                    cnt += right-left
                    left += 1
                else:
                    right -= 1
            return cnt
        
        nums.sort()
        return count(upper)-count(lower-1)

Solution from kamyu104/LeetCode-Solutions · MIT