Watch 10 video solutions for Number of Subsequences That Satisfy the Given Sum Condition, a medium level problem involving Array, Two Pointers, Binary Search. This walkthrough by NeetCode has 38,683 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array of integers nums and an integer target.
Return the number of non-empty subsequences of nums such that the sum of the minimum and maximum element on it is less or equal to target. Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: nums = [3,5,6,7], target = 9 Output: 4 Explanation: There are 4 subsequences that satisfy the condition. [3] -> Min value + max value <= target (3 + 3 <= 9) [3,5] -> (3 + 5 <= 9) [3,5,6] -> (3 + 6 <= 9) [3,6] -> (3 + 6 <= 9)
Example 2:
Input: nums = [3,3,6,8], target = 10 Output: 6 Explanation: 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 Explanation: 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 <= 1051 <= nums[i] <= 1061 <= target <= 106Problem Overview: Given an integer array nums and a target, count the number of non‑empty subsequences where the sum of the minimum and maximum element in that subsequence is less than or equal to the target. The result can be large, so it is returned modulo 1e9 + 7.
Approach 1: Two Pointers with Sorting (Time: O(n log n), Space: O(1) extra)
Sort the array first so the smallest and largest elements of a subsequence are easy to reason about. Use two pointers: left at the start and right at the end. If nums[left] + nums[right] ≤ target, every subset formed by choosing elements between them while fixing nums[left] as the minimum is valid. That contributes 2^(right-left) subsequences. Move left forward to explore the next minimum. If the sum exceeds the target, decrease right to reduce the maximum element. Precompute powers of two to count combinations efficiently.
This approach works because sorting guarantees the smallest element of any chosen subsequence is fixed at left while all elements between left and right are ≤ nums[right]. The scan runs in linear time after sorting. The technique heavily relies on sorting and a classic two pointers sweep.
Approach 2: Dynamic Programming with Binary Indexing (Time: O(n log n), Space: O(n))
Another way is to process numbers in sorted order and maintain counts of valid subsequence boundaries using a Binary Indexed Tree (Fenwick Tree). After sorting, treat each element as a potential maximum. Use binary search to find the largest index where nums[i] + nums[j] ≤ target. A Fenwick Tree stores counts of previously considered elements and helps accumulate how many subsequences can extend with the current value. The DP state essentially counts combinations where the current value acts as the maximum while previously processed values act as potential minimums.
This method is useful when extending the problem to variations that require dynamic frequency updates or range queries. It blends ideas from array processing and indexed prefix sums.
Recommended for interviews: The sorted two‑pointer solution is the expected answer. It reduces the problem to a single linear scan after sorting and uses a simple combinatorial observation with 2^(k). A brute force enumeration of subsequences shows understanding but runs in exponential time. Demonstrating the two‑pointer counting trick signals strong problem‑solving and optimization skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two Pointers with Sorting | O(n log n) | O(1) extra | Best practical solution. Works when the array can be sorted and subsequence count depends on min and max. |
| Dynamic Programming with Binary Indexed Tree | O(n log n) | O(n) | Useful for variations needing prefix queries, dynamic counting, or range updates. |