NeetCode #204LC-1498MediumTwo Pointers
← Back to All Problems#204 · #1498 · Number of Subsequences That Satisfy the Given Sum Condition(满足条件的子序列数目)
📌 Problem Statement & Constraints
Given an array
nums and an integer target, count the number of non-empty subsequences whose minimum plus maximum is at most target. Return the count modulo 10^9 + 7. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^6, 1 <= target <= 10^6.💡 Core Algorithmic Approaches
- Sort the array. Then for a subsequence, only the minimum and maximum matter, and they are the smallest and largest chosen elements.
- Use two pointers: if
nums[l] + nums[r] <= target, then every subsequence whose minimum isnums[l]and whose maximum is at mostnums[r]is valid. The elements strictly betweenlandrare free to be included or excluded, giving2^(r - l)valid subsequences. - Add that count, then advance
l. If the sum is too large, decrementr. - Precompute the powers of two modulo
10^9 + 7so the contribution is O(1) per step.
💻 Benchmark Python3 Implementation
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
MOD = 10 ** 9 + 7
nums.sort()
n = len(nums)
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
pow2[i] = pow2[i - 1] * 2 % MOD
res = 0
l, r = 0, n - 1
while l <= r:
if nums[l] + nums[r] <= target:
# any subset of the elements strictly between l and r works
res = (res + pow2[r - l]) % MOD
l += 1
else:
r -= 1
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort dominates; the two-pointer scan is O(n).
💾 Space Complexity
O(n) for the power table (or O(log MOD) per lookup with fast exponentiation instead).
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the modulo: the count is exponential in n.
- Including the endpoints in the free-choice count: the exponent is
r - l, counting only the elements strictly between the two pointers, because the endpoints are fixed as the min and max. - Enumerating subsequences: 2^n possibilities.
- Using
pow(2, r-l, MOD)inside the loop: correct but O(log MOD) per iteration; precomputing is O(1) per step. - Advancing
rwhen the sum is valid: the correct move is to advancel, since a smaller minimum admits more valid maxima.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.