You are given an array of integers nums and an integer target.
Count every non-empty subsequence of nums whose smallest and largest element together satisfy min + max <= target. A subsequence keeps the relative order of nums but may drop any elements — what matters here is only the two extremes of whatever you pick.
Because the count can be astronomically large, return it modulo 10^9 + 7.
Note that a subsequence is chosen by positions, so equal values at different indices count as different subsequences.
nums[right] - nums[left] <= target, and for each right add 2^(right - left - ... ) style block counts, being careful not to double-count.Input: nums = [3,5,6,7], target = 9 Output: 4 The valid subsequences are [3], [3,5], [3,5,6], [3,6] — each has min + max <= 9.
Input: nums = [3,3,6,8], target = 10 Output: 6 Repeated values count separately: [3], [3], [3,3], [3,6], [3,6], [3,3,6].
Input: nums = [2,3,3,4,6,7], target = 12 Output: 61 There are 63 non-empty subsequences; only [6,7] and [7] break the rule, leaving 61.
- 1 <= nums.length <= 10^5 - 1 <= nums[i] <= 10^6 - 1 <= target <= 10^6
Counting subsequences smells like it demands walking all 2^n of them — impossible at n = 10^5. But a single sort plus two pointers that walk toward each other collapses the entire count into one linear sweep. Here is the arc from the exponential brute force to that trick.
2^k combinations.mod 10^9 + 7 and powers of two are precomputed under that modulus.In plain words: pick any non-empty set of positions. Look only at the smallest and largest values in that set. If their sum is <= target, the set counts. Return how many such sets exist, modulo 10^9 + 7.
Worked example — nums = [3,5,6,7], target = 9
sorted: [3, 5, 6, 7]
fix min = 3 (index 0):
largest partner allowed: 3 + x <= 9 -> x <= 6 -> up to index 2
free middle elements between index 0 and 2: {5, 6} -> 2 of them
subsequences with 3 as min: 2^2 = 4
fix min = 5, 6, 7: 5+5=10 > 9 already fails -> contribute 0
total = 4
Asking before coding shows you have mapped the edges of the problem, not just the happy path.
“Is a subsequence chosen by position, so equal values at different indices are distinct?”
Yes — that is why duplicates multiply the count, and why sorting (which only reorders values) is safe.
“Do the min and max have to be different elements?”
No — a single-element subsequence has min equal to max, so the rule becomes 2 * value <= target.
“What if no subsequence satisfies the rule?”
The answer is 0, which happens when even the smallest element doubled exceeds target.
“Can the empty subsequence count?”
No — only non-empty subsequences are counted.
“How large can nums get?”
Up to 10^5, so an exponential enumeration is out and the answer needs a modulus.
Before I start, let me confirm a couple of things.
Subsequences are picked by index, so repeated values count as separate choices — correct?
And only the minimum and maximum of a chosen set matter for the rule, with the count taken modulo ten to the nine plus seven.
The rule inspects just the min and max of a chosen set. Sorting the array changes nothing about which sets are valid — it only lines the values up so the extremes are trivial to locate. After sorting, a valid group is exactly a window [left, right] that includes both ends.
Sort, then treat nums[left] as the minimum of the group. Find the farthest right with nums[left] + nums[right] <= target. Every element strictly between left and right can independently be in or out, and left itself is always in. That is 2^(right - left) valid subsequences whose minimum is nums[left].
sorted: [ a b c d e ]
^L ^R a + e <= target
| free free free |
subsequences with a as min = 2^(R - L)Start left = 0, right = n - 1. If nums[left] + nums[right] <= target, add 2^(right - left) and advance left. Otherwise the current right is too big for any remaining minimum, so shrink right. Each pointer moves at most n times — one linear sweep after the sort.
| Brute force | Optimal | |
|---|---|---|
| Idea | Enumerate all 2^n subsets | Sort + two pointers, count in blocks |
| Time | O(2^n · n) | O(n log n) |
| Space | O(1) | O(n) |
The full code for both lives in the Approaches selector below.
Key takeaway
When a rule on a set depends only on its extremes, sort and fix one extreme: the elements between the two ends collapse into a 2^k block you can count in O(1) instead of enumerating.
sort(nums); precompute pow2[0..n-1] mod p
left = 0, right = n-1, ans = 0
while left <= right:
if nums[left] + nums[right] <= target:
ans = (ans + pow2[right - left]) mod p
left += 1
else:
right -= 1
return ans