1498. Number of Subsequences That Satisfy the Given Sum Condition

Problem

You are 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 on it is less or equal to **target. Since the answer may be too large, return it *modulo* 109 + 7.

  Example 1:

Input: nums = [3,5,6,7], target = 9
Output: 4
Explanation: There are 4 subsequences that satisfy the condition.
[3] -> Min value + max value <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

Example 2:

Input: nums = [3,3,6,8], target = 10
Output: 6
Explanation: There are 6 subsequences that satisfy the condition. (nums can have repeated numbers).
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

Example 3:

Input: nums = [2,3,3,4,6,7], target = 12
Output: 61
Explanation: There are 63 non-empty subsequences, two of them do not satisfy the condition ([6,7], [7]).
Number of valid subsequences (63 - 2 = 61).

  Constraints:

• 1 <= nums.length <= 105

• 1 <= nums[i] <= 106

• 1 <= target <= 106

Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var numSubseq = function(nums, target) {
    nums.sort((a, b) => a - b);
    var res = 0;
    var l = 0;
    var r = nums.length - 1;
    var mod = Math.pow(10, 9) + 7;
    var pows = Array(nums.length);
    pows[0] = 1;
    for (var i = 1; i < nums.length; i++) {
        pows[i] = (pows[i - 1] * 2) % mod;
    }
    while (l <= r) {
        if (nums[l] + nums[r] <= target) {
            res += pows[r - l];
            res %= mod;
            l++;
        } else {
            r--;
        }
    }
    return res;
};

Explain:

1. sort the array won't change the result, so we sort it first
2. then use two pointer to find out answers
3. keep it in mind: do not let numbers overflow

Complexity:

• Time complexity : O(nlog(n)).
• Space complexity : O(n).