[Leetcode] 2563. Count the Number of Fair Pairs

https://leetcode.com/problems/count-the-number-of-fair-pairs/description/?envType=daily-question&envId=2025-04-19

initial

So there is very obv n^2 sol but i was sure there is better way. So I tried thinking while left<right, I wanna see how many valid combinations I can make by moving left by +1 while fixing right pointer, and moving right by +1 while fixing left pointer. But this didnt work im not sure

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        print(nums)
        length=len(nums)
        ans=0
        def lessThanTarget(target,nums):
            left,right=0,len(nums)-1
            res=0
            while left<right:
                hola= nums[left]+nums[right]
                if hola<target:
                    res+=right-left
                    left+=1
                else:
                    right-=1
            return res
        return lessThanTarget(upper+1,nums)-lessThanTarget(lower,nums)

sol

The key is that if we wanna find the middle interval, we can get the upper boundary and minus the lower boundary to get this middle interval.

For example, if we wanna find 3<=x<=5, in math we do x<6 - x<3 right? This applies to this case. If we find whose sum is less than lower and another sum that is strictly less than upper + 1, we can subtract to get an interval that is equivalent to being in the range [lower, upper].

One important note is the condition to move pointers. lessThanTarget function is designed to count pairs whose sum is strictly less than the target. My wrong comparison is hola > target, and when it's not, you add right - left. This means I am including pairs whose sum is equal to the target. So correct condition should exclude the sum being equal to target.

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        print(nums)
        length=len(nums)
        ans=0
        def lessThanTarget(target,nums):
            left,right=0,len(nums)-1
            res=0
            while left<right:
                hola= nums[left]+nums[right]
                if hola<target:
                    res+=right-left
                    left+=1
                else:
                    right-=1
            return res
        return lessThanTarget(upper+1,nums)-lessThanTarget(lower,nums)

complexity

n log n tme
i thought its defo 1 space but

Space Complexity:

Sorting: The space complexity of the sorting algorithm depends on the specific implementation used by the programming language.
In many standard implementations (like Timsort used in Python), the sorting is done in-place or requires O(logn) auxiliary space in the average case. In the worst case, it might be O(n).
Auxiliary Space: The rest of the algorithm uses a constant amount of extra space for variables like n, ans, left_bound, and right_bound. This is O(1) space.
Therefore, the overall space complexity is dominated by the sorting algorithm. It's typically O(logn) or O(n) depending on the sorting implementation. If the sorting is done in-place without significant extra space, the space complexity would be O(1). However, it's safer to consider the space used by the sorting algorithm.