LeetCode Daily Challenge-1498. Number of Subsequences That Satisfy the Given Sum Condition(Med)

• LeetCode Link
• Topics: Array,Hash Table,Sorting,Heap (Priority Queue)
• Date: 29th June 2025

Problem Overview

This problem asks us to count subsequences where the sum of the minimum and maximum elements is at most target. A subsequence maintains the relative order of elements but doesn't need to be contiguous.

Key Insights

The crucial observation is that we only care about the minimum and maximum elements of each subsequence, not the elements in between. This leads to an elegant two-pointer solution.

Solution Approach

1. Sort the Array

nums.sort()

Sorting allows us to use two pointers effectively. After sorting, for any subarray nums[left:right+1], the minimum is nums[left] and maximum is nums[right].

2. Two-Pointer Strategy

• Left pointer: Represents the minimum element
• Right pointer: Represents the maximum element
• Condition: nums[left] + nums[right] <= target

3. Counting Valid Subsequences

When nums[left] + nums[right] <= target, all subsequences that:

• Start with nums[left] (as minimum)
• End anywhere from left to right (as maximum)
• Include any combination of elements between left and right

are valid. The count is 2^(right - left) because we can choose to include or exclude each of the (right - left) elements between the minimum and maximum.

Algorithm Walkthrough

def numSubseq(self, nums: List[int], target: int) -> int:
    MOD = 10**9 + 7
    nums.sort()
    n = len(nums)

    # Precompute powers of 2 to avoid repeated calculation
    powers = [1] * n
    for i in range(1, n):
        powers[i] = (powers[i-1] * 2) % MOD

    left, right = 0, n - 1
    result = 0

    while left <= right:
        if nums[left] + nums[right] <= target:
            # All subsequences starting with nums[left] and ending
            # anywhere from left to right are valid
            result = (result + powers[right - left]) % MOD
            left += 1
        else:
            # Current max is too large, try smaller max
            right -= 1

    return result

Step-by-Step Execution

Let's trace through nums = [3,5,6,7], target = 9:

1. After sorting: [3,5,6,7]
2. Initial state: left = 0, right = 3
3. Iteration 1: nums[0] + nums[3] = 3 + 7 = 10 > 9 → right--
4. Iteration 2: nums[0] + nums[2] = 3 + 6 = 9 ≤ 9 → Add 2^(2-0) = 4, left++
5. Iteration 3: nums[1] + nums[2] = 5 + 6 = 11 > 9 → right--
6. Iteration 4: left > right → Stop

Result: 4

Optimization Details

Power Precomputation

powers = [1] * n
for i in range(1, n):
    powers[i] = (powers[i-1] * 2) % MOD

Instead of computing pow(2, right-left, MOD) each time (which is O(log n)), we precompute all powers of 2 up to n-1 in O(n) time.

Modular Arithmetic

All operations use MOD = 10^9 + 7 to prevent integer overflow and meet the problem's requirements.

Complexity Analysis

• Time Complexity: O(n log n) for sorting + O(n) for two-pointer traversal = O(n log n)
• Space Complexity: O(n) for the powers array

Why This Works

The key insight is that sorting doesn't change the validity of subsequences since we only care about min/max values. The two-pointer approach efficiently counts all valid combinations by fixing the minimum element and finding all valid maximum elements.

This solution elegantly transforms a potentially exponential problem into a linear scan after sorting, making it both efficient and intuitive.