How to Solve Number of Subsequences That Satisfy the Given Sum Condition

This problem requires finding the total number of subsequences whose minimum and maximum elements sum to at most the target. Start by sorting the array to use two pointers efficiently and precompute powers of two for subsequence counts. Binary search over the valid answer space ensures that each combination of min and max is counted without exceeding time constraints.

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

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.

How GhostInterview Helps

• GhostInterview walks through sorting and two-pointer strategies to reduce O(2^n) approaches to O(n log n).
• It highlights precomputation of powers of two to avoid repeated calculations for subsequence counts.
• Provides targeted feedback on edge cases such as repeated numbers or single-element subsequences.

Topic Pages

• Array
• Two Pointers
• Binary Search
• Sorting

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.