1498. Number of Subsequences That Satisfy the Given Sum Condition

[mah-shamim]

Topics: Array, Two Pointers, Binary Search, Sorting

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

Hint:

1. Sort the array nums.
2. Use two pointers approach: Given an index i (choose it as the minimum in a subsequence) find the maximum j where j ≥ i and nums[i] +nums[j] ≤ target.
3. Count the number of subsequences.

[mah-shamim]

We need to count the number of non-empty subsequences in an array where the sum of the minimum and maximum elements in each subsequence is less than or equal to a given target. Given the constraints, a brute-force approach is infeasible, so we use sorting and a two-pointer technique to efficiently count valid subsequences.

Approach

1. Sort the Array: Sorting helps in efficiently determining the valid subsequences by allowing us to use two pointers to find the range of elements that can form valid subsequences with a given minimum element.
2. Precompute Powers of Two: Since the number of valid subsequences for a given range can be 2^(j-i) (where i is the starting index and j is the ending index of the valid range), we precompute powers of two modulo 10⁹ + 7 up to the maximum possible exponent (the length of the array) for quick access.
3. Two Pointers Technique:
   • Initialize a pointer j starting from the end of the sorted array.
   • For each element at index i (treated as the minimum element in the subsequence), move j leftwards until the sum of the elements at i and j is less than or equal to the target.
   • The valid range from i to j allows any subset of elements between i+1 and j to form subsequences with the element at i. The count of such subsequences is 2^(j-i).
   • Sum these counts for all valid starting indices i.

Let's implement this solution in PHP: 1498. Number of Subsequences That Satisfy the Given Sum Condition

<?php
/**
 * @param Integer[] $nums
 * @param Integer $target
 * @return Integer
 */
function numSubseq($nums, $target) {
    $mod = 1000000007;
    sort($nums);
    $n = count($nums);

    $pow2 = array_fill(0, $n, 1);
    for ($i = 1; $i < $n; $i++) {
        $pow2[$i] = ($pow2[$i-1] * 2) % $mod;
    }

    $j = $n - 1;
    $ans = 0;
    for ($i = 0; $i < $n; $i++) {
        while ($j >= $i && $nums[$i] + $nums[$j] > $target) {
            $j--;
        }
        if ($j < $i) {
            break;
        }
        $ans = ($ans + $pow2[$j - $i]) % $mod;
    }

    return $ans;
}

// Test cases
$nums1 = [3, 5, 6, 7];
$target1 = 9;
echo numSubseq($nums1, $target1) . "\n"; // Output: 4

$nums2 = [3, 3, 6, 8];
$target2 = 10;
echo numSubseq($nums2, $target2) . "\n"; // Output: 6

$nums3 = [2, 3, 3, 4, 6, 7];
$target3 = 12;
echo numSubseq($nums3, $target3) . "\n"; // Output: 61
?>

Explanation:

1. Sorting the Array: The array is sorted to facilitate the two-pointer approach. This ensures that for any element at index i, all subsequent elements are greater than or equal to it, simplifying the process of finding valid maximum elements.
2. Precomputing Powers of Two: The array $pow2 stores 2^k mod 10⁹ + 7 for all k from 0 to n-1. This allows O(1) access to the number of valid subsequences for any range length k.
3. Two Pointers Technique:
   • The pointer j starts at the end of the array. For each i (starting from the beginning), j is moved left until the sum of elements at i and j is within the target.
   • The number of valid subsequences starting with nums[i] is 2^(j-i), as each element between i+1 and j can either be included or excluded.
   • The result is accumulated modulo 10⁹ + 7 to handle large numbers.
4. Early Termination: If j becomes less than i, it means no valid subsequences exist for the remaining elements, so the loop terminates early.

This approach efficiently counts all valid subsequences by leveraging sorting, precomputation, and a two-pointer technique, ensuring optimal performance for large input sizes.

[topugit]

Thanks for solving the problem of "Number of Subsequences That Satisfy the Given Sum Condition"

[mah-shamim]

Thanks