Number of valid subsequences

XXX. Number of Valid Subsequences

Array

Two Pointer

Problem Statement:

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

• A subsequence is obtained by deleting some elements (possibly zero) from the original array
• The answer may be very large, so return it modulo 10^9 + 7

Algorithm:

1. **Sort the array first**:
   • This allows us to use two pointers approach
   • Left pointer will be minimum element
   • Right pointer will be maximum element
2. **Precompute powers of 2**:
   • Calculate 2^i mod (10^9 + 7) for each possible length
   • Used to count number of possible subsequences
3. **Two Pointer Technique**:
   • If sum > target, decrease right pointer
   • If sum ≤ target, add 2^(r-l) subsequences and increase left pointer

Complexity:

Time Complexity: O(n log n) due to sorting
Space Complexity: O(n) for powers array

Implementation:

Java Solution:

public int numSubseq(int[] nums, int target) {
    Arrays.sort(nums);                              // Sort for two pointer approach
    int res = 0, n = nums.length;
    int l = 0, r = n - 1;                          // Left and right pointers
    int mod = (int)1e9 + 7;
    
    // Precompute powers of 2 modulo mod
    int[] pows = new int[n];                       
    pows[0] = 1;
    for (int i = 1; i < n; ++i)
        pows[i] = pows[i - 1] * 2 % mod;
    
    // Two pointer approach
    while (l <= r) {
        if (nums[l] + nums[r] > target) 
            r--;                                    // Sum too large, decrease max element
        else
            res = (res + pows[r - l++]) % mod;     // Add 2^(r-l) subsequences
    }
    return res;
}
                

Python Solution:

def numSubseq(self, nums: List[int], target: int) -> int:
    nums.sort()                                     # Sort for two pointer approach
    n = len(nums)
    mod = 10**9 + 7
    
    # Precompute powers of 2 modulo mod
    pows = [1]                                     
    for i in range(1, n):
        pows.append(pows[-1] * 2 % mod)
    
    # Two pointer approach
    res = 0
    l, r = 0, n - 1
    
    while l <= r:
        if nums[l] + nums[r] > target:
            r -= 1                                  # Sum too large, decrease max element
        else:
            res = (res + pows[r - l]) % mod        # Add 2^(r-l) subsequences
            l += 1
    
    return res
                

C++ Solution:

class Solution {
public:
    int numSubseq(vector& nums, int target) {
        sort(nums.begin(), nums.end());             // Sort for two pointer approach
        int n = nums.size();
        const int mod = 1e9 + 7;
        
        // Precompute powers of 2 modulo mod
        vector pows(n);                        
        pows[0] = 1;
        for(int i = 1; i < n; i++)
            pows[i] = (pows[i-1] * 2) % mod;
        
        // Two pointer approach
        int res = 0;
        int l = 0, r = n - 1;
        
        while(l <= r) {
            if(nums[l] + nums[r] > target)
                r--;                                // Sum too large, decrease max element
            else
                res = (res + pows[r - l++]) % mod;  // Add 2^(r-l) subsequences
        }
        
        return res;
    }
};
                

Explanation:

• **Sorting First**:
  • Makes minimum and maximum elements easily accessible
  • Enables efficient two pointer approach
• **Powers Array**:
  • pows[i] stores 2^i mod (10^9 + 7)
  • Used to count subsequences between l and r
  • Precomputed to avoid repeated calculations
• **Two Pointer Logic**:
  • Left pointer represents minimum element
  • Right pointer represents maximum element
  • When valid pair found, all elements between can be either taken or not