🎇Number of Subsequences That Satisfy the Given Sum Condition LeetCode 1498 (C++ | JavaScript | Python )

#programming #cpp #javascript #python

Hello, algorithm learners! 🧠

Today we’re exploring a classic greedy + two pointers problem from LeetCode — 1498: Number of Subsequences That Satisfy the Given Sum Condition. This one challenges us to count the number of valid subsequences based on a constraint involving the smallest and largest values in the subsequence. Efficient sorting and modular exponentiation will be our tools of choice here!

🧠 Problem Summary

You are given:

An integer array nums of size up to 10⁵
An integer target

You must return the number of non-empty subsequences such that:

min(subsequence) + max(subsequence) <= target

Return the result modulo 10⁹ + 7.

🔍 Intuition

To build a valid subsequence, you need to ensure:

nums[left] + nums[right] <= target

Where nums[left] is the smallest and nums[right] is the largest number in the subsequence.

After sorting, we can use a two-pointer approach:

Start from both ends.
If the smallest + largest is within target, all combinations of elements in-between are valid.

To count combinations, we use:

2^(right - left)

Why? Because for n elements between two fixed points, we can include/exclude each one independently in the subsequence.

🛠️ Approach

Sort the array to simplify the min/max logic.
Use two pointers left and right to check pairs.
Precompute powers of 2 modulo 10⁹ + 7 to avoid recomputation.

💡 C++ Code

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        int n = nums.size(), count = 0, left = 0, right = n-1, mod = 1e9+7;
        ranges::sort(nums);
        vector<int> pows(n, 1);
        for(int i = 1; i < n; i++)
            pows[i] = pows[i-1] * 2 % mod;

        while(left <= right) {
            if(nums[left] + nums[right] > target) right--;
            else count = (count + pows[right - left]) % mod, left++;
        }

        return count;
    }
};

💻 JavaScript Code

var numSubseq = function(nums, target) {
    const mod = 1e9 + 7;
    const n = nums.length;
    nums.sort((a, b) => a - b);

    const pows = Array(n).fill(1);
    for (let i = 1; i < n; ++i)
        pows[i] = pows[i - 1] * 2 % mod;

    let count = 0, left = 0, right = n - 1;
    while (left <= right) {
        if (nums[left] + nums[right] > target) {
            right--;
        } else {
            count = (count + pows[right - left]) % mod;
            left++;
        }
    }

    return count;
};

🐍 Python Code

def numSubseq(nums, target):
    mod = 10**9 + 7
    nums.sort()
    n = len(nums)
    pows = [1] * n
    for i in range(1, n):
        pows[i] = pows[i-1] * 2 % mod

    count, left, right = 0, 0, n - 1
    while left <= right:
        if nums[left] + nums[right] > target:
            right -= 1
        else:
            count = (count + pows[right - left]) % mod
            left += 1

    return count