Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The condition depends only on a subsequence's minimum and maximum, so sorting preserves the count of index selections. Fix the leftmost selected sorted index as the minimum. If it works with the largest remaining candidate, every subset of the intervening positions also works.

Approach

Sort the array and place pointers at both ends. If their sum exceeds target, decrease the right pointer because that maximum cannot work with any remaining minimum. Otherwise include the left element and freely choose among the right - left later positions, contributing 2^(right-left) subsequences, then advance left. Use modular exponentiation and return the count modulo 10^9 + 7. The empty choice of later positions counts a valid singleton, and duplicate values still represent distinct index selections.

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10**9 + 7
        nums.sort()
        l, r = 0, len(nums) - 1
        res = 0

        while l <= r:
            if nums[r] + nums[l] > target:
                r -= 1
            else:
                res += pow(2, r - l, MOD)
                l += 1

        return res % MOD

Complexity analysis

For n values, sorting and up to n modular exponentiations each taking O(log n) time give O(n log n) total time. The displayed implementations use O(1) explicit auxiliary space beyond the output, plus implementation-dependent sorting workspace of up to O(n).