#1498

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Number of Subsequences That Satisfy the Given Sum Condition

Count all non-empty subsequences in an integer array where the sum of the minimum and maximum elements is at most a target value efficiently.

array two pointers binary search sorting

Problem Statement

Given an array of integers nums and an integer target, determine the number of non-empty subsequences where the sum of the minimum and maximum values in the subsequence does not exceed target. Return the count modulo 10^9 + 7 due to potentially large results.

A subsequence is any sequence derived by deleting zero or more elements without changing the order. For example, nums = [3,5,6,7] and target = 9 produces valid subsequences such as [3], [3,5], [3,6], and [3,5,6], yielding a total of 4 valid subsequences.

Examples

Example 1

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

Output: 4

There are 4 subsequences that satisfy the condition. [3] -> Min value + max value (3 + 5 (3 + 6 (3 + 6 <= 9)

Example 2

Input: nums = [3,3,6,8], target = 10

Output: 6

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

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 Approach

Sort the array to simplify range checks

Begin by sorting nums to allow efficient selection of minimum and maximum values using two pointers. This step converts the problem into a predictable order, enabling quick validation of subsequence bounds.

Use two pointers to count valid subsequences

Initialize pointers at the start and end of the sorted array. For each left pointer position, move the right pointer to the largest index where nums[left] + nums[right] ≤ target. The number of subsequences between these pointers is 2^(right - left), capturing all combinations including the left element.

Apply modular arithmetic and precompute powers of two

Since the answer can grow exponentially, precompute powers of two modulo 10^9 + 7 for all possible subsequence lengths. Apply the modulo operation after each addition to maintain correct results and avoid overflow.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n). For each element, the right pointer moves at most n steps in total, giving O(n) for two pointers. Precomputing powers of two takes O(n). Overall time complexity is O(n log n) and space complexity O(n) for powers of two.

What Interviewers Usually Probe

Check if candidate sorts the array before counting subsequences.
See if candidate uses two pointers instead of nested loops to optimize performance.
Watch for correct modular arithmetic to handle large counts.

Common Pitfalls or Variants

Common pitfalls

Forgetting to include subsequences of length one, which are valid by definition.
Failing to handle repeated numbers correctly when counting combinations.
Not applying modulo at each step, leading to integer overflow.

Follow-up variants

Count subsequences where the difference between max and min is at most target instead of sum.
Find subsequences of exactly k elements satisfying min + max ≤ target.
Compute the sum of all valid subsequences modulo 10^9 + 7 rather than counting them.

FAQ

What is the best approach to solve 'Number of Subsequences That Satisfy the Given Sum Condition' efficiently?

Sort the array and use two pointers combined with precomputed powers of two to count valid subsequences modulo 10^9 + 7.

Why do we use powers of two in this problem?

Each element between the left and right pointers can either be included or excluded, giving 2^(right - left) subsequences.

Can this approach handle repeated numbers in the array?

Yes, the method correctly counts all valid subsequences, including those with repeated numbers, since every combination is considered via powers of two.

What if the array length is very large, up to 10^5?

Sorting and two pointers scale efficiently to n = 10^5, giving O(n log n) runtime, suitable for the largest constraints.

Why is modular arithmetic necessary in this problem?

The number of valid subsequences grows exponentially, and modulo 10^9 + 7 prevents integer overflow and keeps results within limits.

terminal

Solution

Solution 1: Sorting + Binary Search

Since the problem is about subsequences and involves the sum of the minimum and maximum elements, we can first sort the array $\textit{nums}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def numSubseq(self, nums: List[int], target: int) -> int:
        mod = 10**9 + 7
        nums.sort()
        n = len(nums)
        f = [1] + [0] * n
        for i in range(1, n + 1):
            f[i] = f[i - 1] * 2 % mod
        ans = 0
        for i, x in enumerate(nums):
            if x * 2 > target:
                break
            j = bisect_right(nums, target - x, i + 1) - 1
            ans = (ans + f[j - i]) % mod
        return ans

Continue Practicing

#1508 range sum of sorted subarray sums #1385 find the distance value between two arrays #1346 check if n and its double exist