LeetCode 1498 - Number of Subsequences That Satisfy the Given Sum Condition

The problem asks us to find the number of non-empty subsequences of a given array nums such that for each subsequence, t

leetcodemediumarraytwo-pointersbinary-searchsorting

LeetCode Problem 1498

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Sorting

Solution

Problem Understanding

The problem asks us to find the number of non-empty subsequences of a given array nums such that for each subsequence, the sum of the minimum and maximum elements is less than or equal to a given target. A subsequence can be obtained by deleting zero or more elements from the array without changing the order of the remaining elements. Since the number of subsequences can grow exponentially, the answer must be returned modulo $10^9 + 7$.

The input nums is an array of integers, potentially containing duplicates, with length up to $10^5$. Each element can be as large as $10^6$, and target can also be up to $10^6$. This means a brute-force approach that generates all subsequences would be computationally infeasible due to exponential growth in the number of subsequences.

Key points include handling repeated elements, ensuring the subsequence is non-empty, and efficiently counting subsequences without enumerating all of them. Edge cases include very small arrays, arrays where all elements are larger than target, and arrays where all elements are smaller than half of target.

Approaches

The brute-force approach would generate all subsequences of nums, compute the minimum and maximum for each, and count the ones satisfying the sum condition. While this is correct, it is impractical because generating all subsequences of an array of length n requires $O(2^n)$ time, which is far too slow for n = 10^5.

The optimal approach leverages sorting and the two-pointer technique combined with precomputed powers of two. Sorting allows us to easily identify the smallest and largest elements in potential subsequences. Using two pointers, one starting at the left (l) and one at the right (r), we can count how many subsequences can be formed with nums[l] as the minimum and any element between l and r as the maximum. The number of subsequences for each valid pair is given by $2^{r-l}$, representing all combinations of the elements in between.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generate all subsequences and check each for min+max condition
Optimal O(n log n) O(n) Sort + two pointers + precompute powers of two for counting subsequences

Algorithm Walkthrough

  1. Sort the input array nums in ascending order. This allows efficient determination of valid minimum and maximum elements for subsequences.

  2. Precompute powers of 2 modulo $10^9 + 7$ up to n since each subsequence count requires computing $2^k$ quickly.

  3. Initialize two pointers: l = 0 for the leftmost (minimum) element and r = n-1 for the rightmost (potential maximum) element.

  4. Initialize count = 0 to store the total number of valid subsequences.

  5. While l <= r, check if nums[l] + nums[r] <= target:

  6. If yes, all subsequences that include nums[l] as the minimum and any subset of elements between l+1 and r are valid. Increment count by 2^(r-l) modulo $10^9 + 7$. Move l to the right by 1.

  7. If no, the current r is too large to pair with l. Move r to the left by 1.

  8. Return count.

Why it works: Sorting guarantees that for a fixed l, if nums[l] + nums[r] > target, any larger value on the right cannot form a valid subsequence. By counting $2^{r-l}$, we account for all combinations of elements between the two pointers. This ensures all valid subsequences are counted exactly once.

Python Solution

from typing import List

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        nums.sort()
        
        # Precompute powers of 2 modulo MOD
        pow2 = [1] * n
        for i in range(1, n):
            pow2[i] = (pow2[i-1] * 2) % MOD
        
        l, r = 0, n - 1
        count = 0
        
        while l <= r:
            if nums[l] + nums[r] <= target:
                count = (count + pow2[r-l]) % MOD
                l += 1
            else:
                r -= 1
        
        return count

The implementation first sorts the array, precomputes powers of two for efficient subsequence counting, and uses two pointers to traverse the array. If the smallest and largest element sum is valid, it counts all subsequences formed with the current l and any elements up to r. Otherwise, it decreases r to try a smaller maximum element.

Go Solution

func numSubseq(nums []int, target int) int {
    const MOD = 1000000007
    n := len(nums)
    sort.Ints(nums)
    
    pow2 := make([]int, n)
    pow2[0] = 1
    for i := 1; i < n; i++ {
        pow2[i] = (pow2[i-1] * 2) % MOD
    }
    
    l, r := 0, n-1
    count := 0
    
    for l <= r {
        if nums[l]+nums[r] <= target {
            count = (count + pow2[r-l]) % MOD
            l++
        } else {
            r--
        }
    }
    
    return count
}

The Go solution mirrors the Python solution closely. Differences include slice initialization and integer arithmetic modulo $10^9 + 7$. Sorting uses sort.Ints, and slice indexing is straightforward. Overflow is avoided using modulo at each multiplication.

Worked Examples

Example 1: nums = [3,5,6,7], target = 9

Step l r nums[l]+nums[r] Action Count
Start 0 3 3+7=10 >9 → r-- 0
0 2 3+6=9 ≤9 → count+=2^(2-0)=4 4
l>r → stop 1 2 4

Example 2: nums = [3,3,6,8], target = 10

Step l r nums[l]+nums[r] Action Count
Start 0 3 3+8=11 >10 → r-- 0
0 0 2 3+6=9 ≤10 → count+=2^(2-0)=4 4
l=1 1 2 3+6=9 ≤10 → count+=2^(2-1)=2 6
l=2 2 2 6+6=12 >10 → r-- 6
stop 6

Example 3: nums = [2,3,3,4,6,7], target = 12

Following the same logic, the final count is 61.

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, two-pointer traversal is O(n), precomputing powers is O(n)
Space O(n) Store precomputed powers of 2

The solution is efficient and scales well with the constraints.

Test Cases

# Provided examples
assert Solution().numSubseq([3,5,6,7], 9) == 4  # Example 1
assert Solution().numSubseq([3,3,6,8], 10) == 6  # Example 2
assert Solution().numSubseq([2,3,3,4,6,7], 12) == 61  # Example 3

# Edge cases
assert Solution().numSubseq([1], 1) == 1  # Single element <= target
assert Solution().numSubseq([1], 0) == 0  # Single element > target
assert Solution().numSubseq([1,1,1,1], 2) == 15  # All subsequences valid
assert Solution().numSubseq([10,20,30], 15) == 0  # No subsequence valid
assert Solution().numSubseq(list(range(1, 21)), 20) >= 1  # Large input
Test Why
Single element <= target Minimum non-empty array case
Single element > target No valid subsequences
All elements equal Checks handling of duplicates
No valid subsequences Tests pruning logic
Larger input Stress test for correctness