[Leetcode] 1498. Number of Subsequences That Satisfy the Given Sum Condition

🗓️ Daily LeetCoding Challenge May, Day 6

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:

        answer = 0

        nums.sort() # O(NlogN)

        left, right = 0, len(nums) - 1
        while left <= right:                         # O(N)
            if nums[left] + nums[right] <= target:
                if (left - right) in [0, 1]:
                    answer += 1
                else:
                    answer += pow(2, right - left)
                left += 1
            else:
                right -= 1
        
        return answer % (10**9 + 7)