⚡Flashcard Drill➔
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

  1. Sort the array. Then for a subsequence, only the minimum and maximum matter, and they are the smallest and largest chosen elements.
  2. Use two pointers: if nums[l] + nums[r] <= target, then every subsequence whose minimum is nums[l] and whose maximum is at most nums[r] is valid. The elements strictly between l and r are free to be included or excluded, giving 2^(r - l) valid subsequences.
  3. Add that count, then advance l. If the sum is too large, decrement r.
  4. Precompute the powers of two modulo 10^9 + 7 so 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 r when the sum is valid: the correct move is to advance l, 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.
🎯 Drill This Card Now➔

🧩 Related Two Pointers Problems