Number of Subsequences That Satisfy the Given Sum Condition
MedPrompt
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 <= 106
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating every possible non-empty subsequence of the input array nums. For each subsequence, we find its minimum and maximum elements and check if their sum is less than or equal to the target. If the condition is met, we increment a counter. This method is the most straightforward to conceptualize but is computationally infeasible for the given constraints.
Algorithm
- Initialize a counter
countto 0. - Generate all non-empty subsequences of
numsusing a recursive or iterative approach. - For each generated subsequence:
- Find its minimum element
min_valand maximum elementmax_val. - If
min_val + max_val <= target, incrementcount.
- Find its minimum element
- Return
countmodulo10^9 + 7.
Walkthrough
The core idea is to explore all possibilities. We can write a recursive function that, at each step, decides whether to include the current element in the subsequence or not. This builds a decision tree that covers all 2^n possible subsequences. For each complete subsequence, we then perform a check.
// This is a conceptual implementation and will time out.class Solution { int count = 0; int target; int[] nums; final int MOD = 1_000_000_007; public int numSubseq(int[] nums, int target) { this.target = target; this.nums = nums; generateSubsequences(0, new java.util.ArrayList<>()); return count; } private void generateSubsequences(int index, java.util.List<Integer> current) { if (index == nums.length) { if (!current.isEmpty()) { int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for (int num : current) { min = Math.min(min, num); max = Math.max(max, num); } if (min + max <= target) { count = (count + 1) % MOD; } } return; } // Decision 1: Exclude nums[index] generateSubsequences(index + 1, current); // Decision 2: Include nums[index] current.add(nums[index]); generateSubsequences(index + 1, current); current.remove(current.size() - 1); // Backtrack }}This method is too slow because the number of subsequences grows exponentially with the size of the input array nums.
Complexity
Time
O(N * 2^N), where N is the length of `nums`. There are `2^N` subsequences, and for each one, finding the minimum and maximum elements takes O(K) time, where K is the length of the subsequence (up to N).
Space
O(N), where N is the length of `nums`. This space is used by the recursion stack and to store the current subsequence being built.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
A more efficient approach starts by recognizing that the order of elements within a subsequence doesn't affect the min/max sum condition. By sorting the input array nums, we can simplify the problem. If we fix the minimum element of a subsequence, nums[i], we only need to ensure the maximum element, nums[j], satisfies nums[i] + nums[j] <= target. Since the array is sorted, we can use binary search to efficiently find the count of valid maximums for each chosen minimum.
Algorithm
- Sort the input array
nums. - Precompute powers of 2 modulo
10^9 + 7and store them in an arraypowers. - Initialize a result counter
countto 0. - Iterate through the sorted array with an index
ifrom0ton-1.- For each
nums[i], treat it as the minimum element of a subsequence. - Use binary search to find the largest index
j >= isuch thatnums[j] <= target - nums[i]. - If such a
jexists, it means any subsequence starting withnums[i]and containing elements from the rangenums[i+1]tonums[j]is valid. - The number of such subsequences is
2^(j-i). Addpowers[j-i]to thecount.
- For each
- Return
count.
Walkthrough
After sorting nums, we iterate through each element nums[i] and consider it as the fixed minimum of our subsequences. For this nums[i], we need to find how many subsequences can be formed. The maximum element of any such subsequence, let's say nums[k], must satisfy nums[i] + nums[k] <= target. This implies nums[k] <= target - nums[i]. We can find the rightmost element nums[j] that satisfies this condition using binary search. Any element between nums[i] and nums[j] can be included in the subsequence. If we fix nums[i] as the minimum, we can freely choose any subset of the elements {nums[i+1], ..., nums[j]}. There are j-i such elements, giving 2^(j-i) possible subsequences. We sum these counts for each i.
To avoid recomputing powers of 2, we pre-calculate them and store them in an array.
import java.util.Arrays; class Solution { public int numSubseq(int[] nums, int target) { int n = nums.length; int MOD = 1_000_000_007; Arrays.sort(nums); long[] powers = new long[n]; powers[0] = 1; for (int i = 1; i < n; i++) { powers[i] = (powers[i - 1] * 2) % MOD; } int count = 0; for (int i = 0; i < n; i++) { int searchVal = target - nums[i]; int left = i, right = n - 1, j = -1; // Binary search for the rightmost index j <= searchVal while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] <= searchVal) { j = mid; left = mid + 1; } else { right = mid - 1; } } if (j >= i) { count = (int)((count + powers[j - i]) % MOD); } } return count; }}Complexity
Time
O(N log N). Sorting takes O(N log N). The main loop runs N times, with a binary search of O(log N) inside, contributing another O(N log N).
Space
O(N) to store the precomputed powers of 2. The space for sorting depends on the implementation, typically O(log N) or O(N).
Trade-offs
Pros
Significantly more efficient than the brute-force approach.
Passes the time limits for the given constraints.
Cons
The overall time complexity is O(N log N), which can be slightly improved upon.
This is the most optimal approach. It builds upon the sorting idea but replaces the repeated binary searches with a more efficient two-pointer technique. After sorting nums, we use a left pointer for the minimum element and a right pointer for the maximum. Because the array is sorted, as left increases, the right pointer can only decrease or stay put, allowing for a single linear scan of the array.
Algorithm
- Sort the input array
nums. - Precompute powers of 2 modulo
10^9 + 7. - Initialize two pointers,
left = 0andright = n-1, and acount = 0. - While
left <= right:- If
nums[left] + nums[right] <= target:- This pair is valid.
nums[left]can be the minimum. The maximum can be any element fromnums[left]tonums[right]. - The number of valid subsequences with
nums[left]as the minimum is2^(right - left). - Add this to
count. - Since we've counted all subsequences with
nums[left]as the minimum, we move to the next potential minimum:left++.
- This pair is valid.
- Else (
nums[left] + nums[right] > target):nums[right]is too large. We need a smaller maximum, so we decrementright.
- If
- Return
count.
Walkthrough
We start by sorting nums. We initialize left to the start of the array and right to the end. The loop continues as long as left <= right.
If nums[left] + nums[right] <= target, we know that nums[left] can be the minimum of a valid subsequence. The maximum of this subsequence can be any element from nums[left] up to nums[right]. This is because if nums[right] works, any nums[k] with k < right will also work since nums[k] <= nums[right]. The subsequences are formed by taking nums[left] and any subset of the elements {nums[left+1], ..., nums[right]}. There are right - left such elements, so we can form 2^(right - left) valid subsequences. We add this to our total count and then increment left because we have found all valid subsequences with nums[left] as the minimum.
If nums[left] + nums[right] > target, the sum is too large. To fix this, we must decrease the sum, which means we need a smaller maximum element. So, we decrement right.
This process efficiently counts all valid subsequences in a single pass after the initial sort.
import java.util.Arrays; class Solution { public int numSubseq(int[] nums, int target) { int n = nums.length; int MOD = 1_000_000_007; Arrays.sort(nums); long[] powers = new long[n + 1]; powers[0] = 1; for (int i = 1; i <= n; i++) { powers[i] = (powers[i - 1] * 2) % MOD; } int count = 0; int left = 0; int right = n - 1; while (left <= right) { if (nums[left] + nums[right] <= target) { count = (int)((count + powers[right - left]) % MOD); left++; } else { right--; } } return count; }}Complexity
Time
O(N log N), dominated by the initial sorting step. The subsequent two-pointer scan takes only O(N) time.
Space
O(N) to store the precomputed powers of 2. Sorting space is typically O(log N) or O(N).
Trade-offs
Pros
Most efficient solution with an optimal time complexity.
The two-pointer scan is O(N), which is faster than the O(N log N) loop in the binary search approach.
Cons
The main bottleneck is the initial sorting step, which is hard to avoid for this problem.
Solutions
Solution
class Solution {public int numSubseq(int[] nums, int target) { Arrays.sort(nums); final int mod = (int)1 e9 + 7; int n = nums.length; int[] f = new int[n + 1]; f[0] = 1; for (int i = 1; i <= n; ++i) { f[i] = (f[i - 1] * 2) % mod; } int ans = 0; for (int i = 0; i < n; ++i) { if (nums[i] * 2L > target) { break; } int j = search(nums, target - nums[i], i + 1) - 1; ans = (ans + f[j - i]) % mod; } return ans; }private int search(int[] nums, int x, int left) { int right = nums.length; while (left < right) { int mid = (left + right) >> 1; if (nums[mid] > x) { right = mid; } else { left = mid + 1; } } return left; }}class Solution {public: int numSubseq(vector<int> &nums, int target) { sort(nums.begin(), nums.end()); const int mod = 1e9 + 7; int n = nums.size(); int f[n + 1]; f[0] = 1; for (int i = 1; i <= n; ++i) { f[i] = (f[i - 1] * 2) % mod; } int ans = 0; for (int i = 0; i < n; ++i) { if (nums[i] * 2L > target) { break; } int j = upper_bound(nums.begin() + i + 1, nums.end(), target - nums[i]) - nums.begin() - 1; ans = (ans + f[j - i]) % mod; } return ans; }};class Solution: def numSubseq(self, nums: List[int], target: int) -> int: mod = 10 ** 9 + 7 nums . sort() n = len(nums) f = [1] + [0] * n for i in range(1, n + 1): f[i] = f[i - 1] * 2 % mod ans = 0 for i, x in enumerate(nums): if x * 2 > target: break j = bisect_right(nums, target - x, i + 1) - 1 ans = (ans + f[j - i]) % mod return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.