Number of Subsequences That Satisfy the Given Sum Condition solution and explanation
Infosys
Google
9 more videos on this problem
Leetcode 1498 - Number of Subsequences That Satisfy the Given Sum Condition - PythonNeetCode · 8:52 · 39K views
Number of Subsequences That Satisfy the Given Sum Condition | AMAZON | Leetcode - 1498 | Live CodingcodestorywithMIK · 34:54 · 27K views
Leetcode 1498. Number of Subsequences That Satisfy the Given Sum ConditionFraz · 19:02 · 12K views
Number of Subsequences That Satisfy the Given Sum Condition || Binary Exponentiation || Two PointersAryan Mittal · 36:16 · 7K views
Number of Subsequences That Satisfy the Given Sum Condition | Leetcode 1498Techdose · 13:11 · 5K views
Number of Subsequences That Satisfy the Given Sum Condition | Leetcode - 1498Algorithms Made Easy · 11:32 · 2K views
1498. Number of Subsequences That Satisfy the Given Sum Condition | LeetCode Daily Challenge | POTDDeep Tech · 17:51 · 1K views
LeetCode 1498. Number of Subsequences That Satisfy the Given Sum ConditionHappy Coding · 17:59 · 1K views
Number of Subsequences That Satisfy the Given Sum Condition - Leetcode 1498 - PythonTechError · 5:22 · 1K views
1498. Number of Subsequences That Satisfy the Given Sum Condition (Leetcode Medium)Programming Live with Larry · 5:27 · 908 views
The problem
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
Approach overview
Problem 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 1: Two Pointers with Sorting
This approach involves sorting the array and then using a two pointers method to determine valid subsequences. We focus on the potential minimum and maximum values in a subsequence.
After sorting, use two pointers, one starting from the beginning of the array (for the minimum) and the other from the end (for the maximum). For each minimum, the number of valid subsequences is determined by how many elements from the minimum can pair with elements from the maximum such that their sum is less than or equal to the target. The number of subsequences can be calculated using the binary exponentiation of 2 with the distance between the two pointers.
from typing import List
MOD = 10**9 + 7
class Solution:
def power(self, x: int, y: int, p: int) -> int:
res = 1
x = x % p
while y > 0:
if y & 1:
res = (res * x) % p
x = (x * x) % p
y >>= 1
return res
def numSubseq(self, nums: List[int], target: int) -> int:
nums.sort()
result = 0
left, right = 0, len(nums) - 1
while left <= right:
if nums[left] + nums[right] <= target:
result = (result + self.power(2, right - left, MOD)) % MOD
left += 1
else:
right -= 1
return result
# Example usage:
solution = Solution()
nums = [3, 5, 6, 7]
target = 9
print(solution.numSubseq(nums, target))import java.util.Arrays;
public class Solution {
private static final int MOD = 1000000007;
private long power(int base, int exp, int mod) {
long result = 1;
long x = base % mod;
while (exp > 0) {
if ((exp & 1) == 1) {
result = (result * x) % mod;
}
x = (x * x) % mod;
exp >>= 1;
}
return result;
}
public int numSubseq(int[] nums, int target) {
Arrays.sort(nums);
long result = 0;
int left = 0, right = nums.length - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power(2, right - left, MOD)) % MOD;
left++;
} else {
right--;
}
}
return (int) result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {3, 5, 6, 7};
int target = 9;
System.out.println(solution.numSubseq(nums, target));
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define MOD 1000000007
long power(int x, int y, int p) {
long res = 1;
x = x % p;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
int numSubseq(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
long result = 0;
int left = 0, right = nums.size() - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power(2, right - left, MOD)) % MOD;
left++;
} else {
right--;
}
}
return (int)result;
}
int main() {
vector<int> nums = {3, 5, 6, 7};
int target = 9;
cout << numSubseq(nums, target) << endl;
return 0;
}const MOD = 1000000007;
function power(x, y, p) {
let res = 1;
x = x % p;
while (y > 0) {
if (y & 1) res = (res * x) % p;
x = (x * x) % p;
y >>= 1;
}
return res;
}
var numSubseq = function(nums, target) {
nums.sort((a, b) => a - b);
let result = 0;
let left = 0, right = nums.length - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power(2, right - left, MOD)) % MOD;
left++;
} else {
right--;
}
}
return result;
};
// Example usage:
const nums = [3, 5, 6, 7];
const target = 9;
console.log(numSubseq(nums, target));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MOD 1000000007
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
long power(int x, int y, int p) {
long res = 1;
x = x % p;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
int numSubseq(int *nums, int numsSize, int target) {
qsort(nums, numsSize, sizeof(int), compare);
long result = 0;
int left = 0, right = numsSize - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power(2, right - left, MOD)) % MOD;
left++;
} else {
right--;
}
}
return (int)result;
}
int main() {
int nums[] = {3, 5, 6, 7};
int target = 9;
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", numSubseq(nums, size, target));
return 0;
}using System;
public class Solution {
private const int MOD = 1000000007;
private long Power(int x, int y, int p) {
long result = 1;
long baseValue = x % p;
while (y > 0) {
if ((y & 1) == 1) {
result = (result * baseValue) % p;
}
baseValue = (baseValue * baseValue) % p;
y >>= 1;
}
return result;
}
public int NumSubseq(int[] nums, int target) {
Array.Sort(nums);
long count = 0;
int left = 0, right = nums.Length - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
count = (count + Power(2, right - left, MOD)) % MOD;
left++;
} else {
right--;
}
}
return (int)count;
}
public static void Main(string[] args) {
var solution = new Solution();
int[] nums = {3, 5, 6, 7};
int target = 9;
Console.WriteLine(solution.NumSubseq(nums, target));
}
}Python's solution includes a helper method for fast exponentiation using iterative binary power, optimizing large modulus calculations. Utilizing sort sorts the input list, while two pointers shift through the array determining valid subsequences whose minimum and maximum meet the sum criteria under the target.
Time Complexity: O(n log n), arising from sorting the array.
Space Complexity: O(1), besides input space.
Approach 2: Dynamic Programming with Binary Indexing
This approach involves dynamic programming where pre-computed powers of 2 are used to calculate valid subsequences. Using arrays to store results dynamically avoids repetitive calculations and exploits binary indexing for faster computation on potential subsets.
The idea is to create a precompute power array of size n to store power values of 2 up to n. Iterating with this precompute allows identifying valid subsequences without recalculating powers each iteration, enhancing efficiency especially for extremely large arrays.
from typing import List
MOD = 10**9 + 7
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
power_2 = [1] * n
for i in range(1, n):
power_2[i] = power_2[i - 1] * 2 % MOD
result = 0
left, right = 0, n - 1
while left <= right:
if nums[left] + nums[right] <= target:
result = (result + power_2[right - left]) % MOD
left += 1
else:
right -= 1
return result
# Example usage:
solution = Solution()
nums = [3, 5, 6, 7]
target = 9
print(solution.numSubseq(nums, target))import java.util.Arrays;
public class Solution {
private static final int MOD = 1000000007;
public int numSubseq(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
long[] power_2 = new long[n];
power_2[0] = 1;
for (int i = 1; i < n; i++) {
power_2[i] = (power_2[i - 1] * 2) % MOD;
}
long result = 0;
int left = 0, right = nums.length - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power_2[right - left]) % MOD;
left++;
} else {
right--;
}
}
return (int) result;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {3, 5, 6, 7};
int target = 9;
System.out.println(solution.numSubseq(nums, target));
}
}#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define MOD 1000000007
int numSubseq(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<long> power_2(nums.size(), 0);
power_2[0] = 1;
for (size_t i = 1; i < nums.size(); ++i) {
power_2[i] = (power_2[i - 1] * 2) % MOD;
}
long result = 0;
int left = 0, right = nums.size() - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power_2[right - left]) % MOD;
left++;
} else {
right--;
}
}
return (int)result;
}
int main() {
vector<int> nums = {3, 5, 6, 7};
int target = 9;
cout << numSubseq(nums, target) << endl;
return 0;
}const MOD = 1000000007;
var numSubseq = function(nums, target) {
nums.sort((a, b) => a - b);
const n = nums.length;
const power_2 = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
power_2[i] = (power_2[i - 1] * 2) % MOD;
}
let result = 0;
let left = 0, right = n - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power_2[right - left]) % MOD;
left++;
} else {
right--;
}
}
return result;
};
// Example usage:
const nums = [3, 5, 6, 7];
const target = 9;
console.log(numSubseq(nums, target));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MOD 1000000007
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
long power(int x, int y, int p) {
long res = 1;
x = x % p;
while (y > 0) {
if (y & 1)
res = (res * x) % p;
y = y >> 1;
x = (x * x) % p;
}
return res;
}
int numSubseq(int *nums, int numsSize, int target) {
qsort(nums, numsSize, sizeof(int), compare);
long *power_2 = malloc(numsSize * sizeof(long));
power_2[0] = 1;
for (int i = 1; i < numsSize; i++) {
power_2[i] = (power_2[i - 1] * 2) % MOD;
}
long result = 0;
int left = 0, right = numsSize - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power_2[right - left]) % MOD;
left++;
} else {
right--;
}
}
free(power_2);
return (int)result;
}
int main() {
int nums[] = {3, 5, 6, 7};
int target = 9;
int size = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", numSubseq(nums, size, target));
return 0;
}using System;
public class Solution {
private const int MOD = 1000000007;
public int NumSubseq(int[] nums, int target) {
Array.Sort(nums);
int n = nums.Length;
long[] power_2 = new long[n];
power_2[0] = 1;
for (int i = 1; i < n; i++) {
power_2[i] = (power_2[i - 1] * 2) % MOD;
}
long result = 0;
int left = 0, right = nums.Length - 1;
while (left <= right) {
if (nums[left] + nums[right] <= target) {
result = (result + power_2[right - left]) % MOD;
left++;
} else {
right--;
}
}
return (int)result;
}
public static void Main(string[] args) {
var solution = new Solution();
int[] nums = {3, 5, 6, 7};
int target = 9;
Console.WriteLine(solution.NumSubseq(nums, target));
}
}Python's version of the algorithm sorts the input, establishes precomputed powers, and then evaluates subsequences using these precomputed values instead of recalculating them, optimizing its run within the loop where two pointers iterate through the array, processing validity.
Time Complexity: O(n log n) because of sorting, added O(n) for precomputation.
Space Complexity: O(n) due to storing powers of 2.
Approach 3: Sorting + Binary Search
Since the problem is about subsequences and involves the sum of the minimum and maximum elements, we can first sort the array nums.
Then we enumerate the minimum element nums[i]. For each nums[i], we can find the maximum element nums[j] in nums[i + 1] to nums[n - 1] such that nums[i] + nums[j] leq target. The number of valid subsequences in this case is 2^{j - i}, where 2^{j - i} represents all possible subsequences from nums[i + 1] to nums[j]. We sum up the counts of all such subsequences.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array nums.
function numSubseq(nums: number[], target: number): number {
nums.sort((a, b) => a - b);
const mod = 1e9 + 7;
const n = nums.length;
const f: number[] = Array(n + 1).fill(1);
for (let i = 1; i <= n; ++i) {
f[i] = (f[i - 1] * 2) % mod;
}
let ans = 0;
for (let i = 0; i < n && nums[i] * 2 <= target; ++i) {
const j = search(nums, target - nums[i], i + 1) - 1;
if (j >= i) {
ans = (ans + f[j - i]) % mod;
}
}
return ans;
}
function search(nums: number[], x: number, left: number): number {
let right = nums.length;
while (left < right) {
const mid = (left + right) >> 1;
if (nums[mid] > x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}func numSubseq(nums []int, target int) (ans int) {
sort.Ints(nums)
n := len(nums)
f := make([]int, n+1)
f[0] = 1
const mod int = 1e9 + 7
for i := 1; i <= n; i++ {
f[i] = f[i-1] * 2 % mod
}
for i, x := range nums {
if x*2 > target {
break
}
j := sort.SearchInts(nums[i+1:], target-x+1) + i
ans = (ans + f[j-i]) % mod
}
return
}impl Solution {
pub fn num_subseq(mut nums: Vec<i32>, target: i32) -> i32 {
nums.sort();
const MOD: i32 = 1_000_000_007;
let n = nums.len();
let mut f = vec![1; n + 1];
for i in 1..=n {
f[i] = (f[i - 1] * 2) % MOD;
}
let mut ans = 0;
for i in 0..n {
if nums[i] * 2 > target {
break;
}
let mut l = i + 1;
let mut r = n;
while l < r {
let m = (l + r) / 2;
if nums[m] > target - nums[i] {
r = m;
} else {
l = m + 1;
}
}
let j = l - 1;
ans = (ans + f[j - i]) % MOD;
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two Pointers with Sorting | Time Complexity: O(n log n), arising from sorting the array. |
| Dynamic Programming with Binary Indexing | Time Complexity: O(n log n) because of sorting, added O(n) for precomputation. |
| Sorting + Binary Search | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Number of Subsequences That Satisfy the Given Sum Condition easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 49%. The difficulty comes from recognizing that once the minimum and maximum satisfy the constraint, every subset of the middle elements forms a valid subsequence, leading to the 2^(k) counting trick.
Number of Subsequences That Satisfy the Given Sum Condition Python/Java solution
Most implementations sort the array, precompute powers of two modulo 1e9+7, and move two pointers inward. Python, Java, C++, and JavaScript solutions follow the same structure: sort, maintain left and right indices, and accumulate counts when nums[left] + nums[right] ≤ target.
How to solve Number of Subsequences That Satisfy the Given Sum Condition in O(n)?
A strictly O(n) solution is not possible because the input must be sorted to efficiently control the minimum and maximum elements of subsequences. The closest optimal approach is O(n log n): sort the array, then use two pointers to count valid subsequences using precomputed powers of two.
What is the best approach for Number of Subsequences That Satisfy the Given Sum Condition?
The optimal approach sorts the array and uses a two pointers scan. Fix the smallest element with a left pointer and try the largest possible element with a right pointer. If their sum is ≤ target, all subsequences between them are valid and contribute 2^(right-left) combinations. This runs in O(n log n) time due to sorting and O(1) extra space.
Is Number of Subsequences That Satisfy the Given Sum Condition asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at large tech companies including Amazon, Google, and Meta because it tests sorting, two pointers, and combinatorial counting. Interviewers expect candidates to recognize the min–max constraint and transform the problem into a sorted two‑pointer scan.
What data structure is used in Number of Subsequences That Satisfy the Given Sum Condition?
The primary technique uses arrays with sorting and a two‑pointer traversal. Some alternative implementations use a Binary Indexed Tree (Fenwick Tree) for prefix counting combined with binary search. The key observation is managing minimum and maximum elements efficiently.
What is the time complexity of Number of Subsequences That Satisfy the Given Sum Condition?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, the two‑pointer traversal processes the array in O(n). Precomputing powers of two also takes O(n), keeping the overall complexity O(n log n) with O(n) auxiliary storage for powers.