Problem Description

Given an array of integers nums and an integer target, you are to count the number of non-empty subsequences such that the sum of the minimum and maximum elements in the subsequence is less than or equal to target.

A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. You may not reuse elements, and each subsequence is considered distinct based on the indices of chosen elements.

Since the answer can be very large, return it modulo 10^9 + 7.

Constraints:

• 1 ≤ nums.length ≤ 10⁵
• 1 ≤ nums[i] ≤ 10⁶
• 1 ≤ target ≤ 10⁶

Thought Process

The brute-force way would be to generate every possible subsequence, check its minimum and maximum, and count if their sum is within the target. However, this is not feasible for large arrays since the number of subsequences is exponential (2ⁿ).

We need to find a way to efficiently count the valid subsequences without explicitly generating them. Sorting the array helps because for any chosen minimum, the possible maximums are always to its right. We can then use two pointers to efficiently find the range of valid subsequences for each minimum.

The challenge is to count all subsequences where the minimum is at the current left pointer and the maximum is at the current right pointer, and their sum is within the limit. For each such pair, all combinations of the elements between them (inclusive) are valid subsequences.

Solution Approach

• Step 1: Sort the Array
  Sorting nums allows us to easily identify the minimum and maximum of any subsequence by their positions.
• Step 2: Two Pointers
  Initialize two pointers: left at the start (smallest number) and right at the end (largest number).
• Step 3: Precompute Powers of 2
  Since the number of ways to choose elements between left and right is 2^right-left, we precompute all powers of 2 up to n modulo 10⁹+7 for efficiency.
• Step 4: Iterate and Count
  While left ≤ right:
  • If nums[left] + nums[right] ≤ target, then every subsequence that starts with nums[left], ends with nums[right], and uses any combination of elements in between is valid. There are 2^right-left such subsequences. Add this count to the answer and increment left.
  • Otherwise, decrement right to try a smaller maximum.
• Step 5: Return the Result
  Return the total count modulo 10⁹+7.

This approach ensures that each valid subsequence is counted exactly once and leverages sorting and combinatorics for efficiency.

Example Walkthrough

Let's consider nums = [3, 5, 6, 7] and target = 9.

1. Sort nums: [3, 5, 6, 7]
2. Initialize left = 0, right = 3 (pointing to 3 and 7).
3. Check nums[0] + nums[3] = 3 + 7 = 10 > 9. So, decrement right to 2.
4. Check nums[0] + nums[2] = 3 + 6 = 9 ≤ 9. There are 2^2-0 = 4 subsequences:
   • [3], [3,5], [3,6], [3,5,6]
   Add 4 to the answer. Increment left to 1.
5. Check nums[1] + nums[2] = 5 + 6 = 11 > 9. Decrement right to 1.
6. Now left = right = 1. nums[1] + nums[1] = 10 > 9. Decrement right to 0.
7. Loop ends. The answer is 4.

This matches the expected number of valid subsequences.

Time and Space Complexity

• Brute-Force Approach: O(2ⁿ * n) time (generating all subsequences and checking min/max), O(n) space for recursion stack.
• Optimized Approach:
  • Time: O(n log n) for sorting + O(n) for the two pointers loop + O(n) for precomputing powers = O(n log n) total.
  • Space: O(n) for the powers array and sorting.

The optimized approach is feasible for large inputs due to its efficiency.

Summary

By sorting the array and using a two-pointer approach, we efficiently count all valid subsequences where the sum of the minimum and maximum is within the target. Precomputing powers of two allows us to quickly count combinations without generating subsequences. This method transforms a seemingly exponential problem into a manageable O(n log n) solution, making it both elegant and practical for large inputs.

Code Implementation

MOD = 10**9 + 7

class Solution:
    def numSubseq(self, nums, target):
        nums.sort()
        n = len(nums)
        pow2 = [1] * (n)
        for i in range(1, n):
            pow2[i] = pow2[i-1] * 2 % MOD
        
        left, right = 0, n - 1
        ans = 0
        while left <= right:
            if nums[left] + nums[right] <= target:
                ans = (ans + pow2[right - left]) % MOD
                left += 1
            else:
                right -= 1
        return ans
      

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        const int MOD = 1e9 + 7;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<int> pow2(n, 1);
        for (int i = 1; i < n; ++i)
            pow2[i] = pow2[i - 1] * 2 % MOD;
        int left = 0, right = n - 1, ans = 0;
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                ans = (ans + pow2[right - left]) % MOD;
                ++left;
            } else {
                --right;
            }
        }
        return ans;
    }
};
      

class Solution {
    public int numSubseq(int[] nums, int target) {
        int MOD = 1_000_000_007;
        Arrays.sort(nums);
        int n = nums.length;
        int[] pow2 = new int[n];
        pow2[0] = 1;
        for (int i = 1; i < n; ++i) {
            pow2[i] = (pow2[i - 1] * 2) % MOD;
        }
        int left = 0, right = n - 1, ans = 0;
        while (left <= right) {
            if (nums[left] + nums[right] <= target) {
                ans = (ans + pow2[right - left]) % MOD;
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }
}
      

var numSubseq = function(nums, target) {
    const MOD = 1e9 + 7;
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const pow2 = new Array(n).fill(1);
    for (let i = 1; i < n; ++i) {
        pow2[i] = pow2[i - 1] * 2 % MOD;
    }
    let left = 0, right = n - 1, ans = 0;
    while (left <= right) {
        if (nums[left] + nums[right] <= target) {
            ans = (ans + pow2[right - left]) % MOD;
            left++;
        } else {
            right--;
        }
    }
    return ans;
};