Problem Description

You have an array of integers nums and an integer target.

Your task is to count how many non-empty subsequences of nums satisfy this condition: when you take the minimum and maximum elements from the subsequence and add them together, their sum must be less than or equal to target.

A subsequence means you can pick any elements from the array while keeping their original order, but you don't have to pick consecutive elements. For example, if nums = [3, 5, 6], then [3], [5], [6], [3, 5], [3, 6], [5, 6], and [3, 5, 6] are all valid subsequences.

For each subsequence you form, you need to:

1. Find the minimum element in that subsequence
2. Find the maximum element in that subsequence
3. Check if minimum + maximum ≤ target

Count all subsequences that meet this condition and return the count modulo 10^9 + 7 (since the answer could be very large).

For example, if nums = [3, 5, 6, 7] and target = 9:

• Subsequence [3, 5] has min=3, max=5, sum=8 ≤ 9 ✓
• Subsequence [3, 5, 6] has min=3, max=6, sum=9 ≤ 9 ✓
• Subsequence [3, 6, 7] has min=3, max=7, sum=10 > 9 ✗
• And so on...

The solution leverages the fact that after sorting, for each minimum element, we can use binary search to find the rightmost valid maximum element, and all elements between them can be either included or excluded in the subsequence, giving us 2^(j-i) valid subsequences for that particular minimum.

Intuition

The key insight is that in any subsequence, only the minimum and maximum elements matter for our condition. This means we don't care about the values of elements between them - we only need to count how many different ways we can select them.

Let's think about this step by step:

1. Why sorting helps: If we sort the array, we can easily identify which element would be the minimum and which would be the maximum in any subsequence. In a sorted array, for any subsequence containing elements from index i to index j, we know nums[i] is the minimum and nums[j] is the maximum.

2. Fixing the minimum: Once we fix nums[i] as the minimum element of our subsequence, we need to find all valid maximum elements. Since the array is sorted, any element nums[j] where j > i could potentially be the maximum, as long as nums[i] + nums[j] ≤ target.

3. Finding the boundary: For a fixed minimum nums[i], there's a rightmost index j where nums[i] + nums[j] ≤ target. Any element beyond this index would violate our condition. We can find this boundary efficiently using binary search.

4. Counting subsequences: Here's the clever part - once we have a valid range from i to j, how many subsequences are there? We must include nums[i] (the minimum) and nums[j] (the maximum), but for every element between them (indices i+1 to j-1), we have a choice: include it or not. This gives us 2^(j-i) different subsequences for this particular minimum and maximum pair.

5. Early termination: If nums[i] * 2 > target, it means even the smallest possible sum (when min = max = nums[i]) exceeds the target, so we can stop our search early.

The pre-computed powers of 2 in array f help us avoid recalculating 2^k repeatedly, making the solution more efficient.

Learn more about Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation follows the sorting and binary search strategy outlined in the reference approach:

Step 1: Preprocessing

• Sort the array nums in ascending order
• Pre-compute powers of 2 up to n and store them in array f, where f[i] = 2^i % mod
  • This avoids redundant power calculations during the main loop
  • Each f[i] = f[i-1] * 2 % mod

Step 2: Main Algorithm For each index i in the sorted array:

1. Set minimum element: Consider nums[i] as the minimum element of the subsequence

2. Early termination check: If nums[i] * 2 > target, break the loop

   • This means even a subsequence with just nums[i] (where min = max) exceeds the target
   • Since the array is sorted, all subsequent elements will also fail this check

3. Find maximum valid index: Use binary search to find the rightmost index j where nums[i] + nums[j] ≤ target

   • bisect_right(nums, target - nums[i], i + 1) finds the insertion point for target - nums[i]
   • Subtract 1 to get the actual index of the largest valid element
   • Search starts from i + 1 since we need j > i

4. Count valid subsequences: For the range [i, j], add 2^(j-i) to the answer

   • We must include nums[i] (minimum) and nums[j] (maximum)
   • For the j - i - 1 elements between them, each can be either included or excluded
   • This gives us 2^(j-i) total subsequences
   • Access the pre-computed value using f[j - i]

5. Apply modulo: Keep the answer within bounds using mod = 10^9 + 7

Time Complexity: O(n log n) for sorting + O(n log n) for n binary searches = O(n log n)

Space Complexity: O(n) for storing the powers of 2

Example Walkthrough

Let's walk through a concrete example with nums = [3, 5, 6, 7] and target = 9.

Step 1: Sort and Precompute Powers of 2

• Array is already sorted: [3, 5, 6, 7]
• Precompute powers of 2: f = [1, 2, 4, 8, 16] where f[k] = 2^k

Step 2: Process Each Element as Minimum

Iteration 1: i = 0, minimum = 3

• Check early termination: 3 * 2 = 6 ≤ 9, so continue
• Find maximum valid index using binary search:
  • Looking for largest j where nums[j] ≤ 9 - 3 = 6
  • Binary search finds j = 2 (nums[2] = 6)
• Count subsequences from index 0 to 2:
  • We have elements [3, 5, 6] where 3 is min, 6 is max
  • Number of subsequences = 2^(2-0) = 2^2 = 4
  • These subsequences are:
    1. [3, 6] - must include min and max
    2. [3, 5, 6] - include the middle element
    3. Actually, let me recalculate: for range [0,2], we fix nums[0]=3 as min and nums[2]=6 as max
    4. Between them we have 1 element (nums[1]=5) which can be included or excluded
    5. So we have 2^1 = 2 subsequences: [3, 6] and [3, 5, 6]
• Wait, I need to correct this. The formula is 2^(j-i-1) for elements between, but the code uses f[j-i]. Let me reconsider.
• Actually, looking at the code, it adds f[j - i] which is 2^(j-i). For j=2, i=0: f[2] = 4
• This counts all subsequences where 3 is minimum and any element up to index 2 can be maximum:
  • [3] (min=max=3, sum=6)
  • [3, 5] (min=3, max=5, sum=8)
  • [3, 6] (min=3, max=6, sum=9)
  • [3, 5, 6] (min=3, max=6, sum=9)
• Total so far: 4

Iteration 2: i = 1, minimum = 5

• Check early termination: 5 * 2 = 10 > 9, so break
• Since even the smallest possible sum (5+5=10) exceeds target, we stop

Final Answer: 4

The valid subsequences are:

1. [3] with min=3, max=3, sum=6 ≤ 9 ✓
2. [3, 5] with min=3, max=5, sum=8 ≤ 9 ✓
3. [3, 6] with min=3, max=6, sum=9 ≤ 9 ✓
4. [3, 5, 6] with min=3, max=6, sum=9 ≤ 9 ✓

Note how the algorithm efficiently counts these without explicitly generating each subsequence. By fixing the minimum element and finding the valid range for the maximum, it uses the power of 2 formula to count all possibilities at once.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity breaks down as follows:

• Sorting the array takes O(n × log n) time
• Pre-computing powers of 2 in array f takes O(n) time
• The main loop iterates through each element once, taking O(n) iterations
• Inside each iteration, bisect_right performs binary search, which takes O(log n) time
• Overall: O(n × log n) + O(n) + O(n × log n) = O(n × log n)

Space Complexity: O(n)

The space complexity consists of:

• Array f stores n + 1 precomputed powers of 2, requiring O(n) space
• The sorting operation may use O(log n) to O(n) auxiliary space depending on the implementation (Python's Timsort uses up to O(n) in worst case)
• Other variables (mod, n, ans, i, x, j) use O(1) space
• Overall: O(n) space is required

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Power of 2 Calculation Without Modulo

A critical mistake is computing powers of 2 without applying modulo during the precomputation phase. This leads to integer overflow for large values of n.

Incorrect Implementation:

# This will cause overflow for large n
power_of_two = [1] * n
for i in range(1, n):
    power_of_two[i] = power_of_two[i - 1] * 2  # Missing modulo!

Correct Implementation:

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

2. Off-by-One Error in Binary Search

Forgetting to subtract 1 from bisect_right result leads to including an invalid element that makes the sum exceed the target.

Incorrect Implementation:

# This includes an element where nums[i] + nums[right_idx] > target
right_idx = bisect_right(nums, target - nums[i], left_idx + 1)

Correct Implementation:

# Subtract 1 to get the actual last valid index
right_idx = bisect_right(nums, target - nums[i], left_idx + 1) - 1

3. Wrong Search Range in Binary Search

Starting the binary search from index left_idx instead of left_idx + 1 causes the algorithm to count single-element subsequences incorrectly or double-count certain subsequences.

Incorrect Implementation:

# This searches from the current minimum element itself
right_idx = bisect_right(nums, target - nums[i], left_idx) - 1

Correct Implementation:

# Start search from the next element after minimum
right_idx = bisect_right(nums, target - nums[i], left_idx + 1) - 1

4. Forgetting to Sort the Array

The algorithm relies on the sorted property to correctly identify min/max elements and perform binary search. Without sorting, the logic completely breaks down.

Incorrect Implementation:

def numSubseq(self, nums: List[int], target: int) -> int:
    # Missing nums.sort()!
    n = len(nums)
    # Rest of the code...

Correct Implementation:

def numSubseq(self, nums: List[int], target: int) -> int:
    nums.sort()  # Essential for the algorithm to work
    n = len(nums)
    # Rest of the code...

5. Incorrect Subsequence Count Formula

Using 2^(j-i-1) instead of 2^(j-i) undercounts valid subsequences by not accounting for all possible combinations of intermediate elements.

Incorrect Implementation:

# This formula is wrong - it doesn't count all valid subsequences
subsequence_count = power_of_two[right_idx - left_idx - 1]

Correct Implementation:

# Correct formula: 2^(number of elements between and including boundaries)
subsequence_count = power_of_two[right_idx - left_idx]