1498. Number of Subsequences That Satisfy the Given Sum Condition
Problem Description
We are given an array nums
of integers and another integer target
. Our goal is to compute the number of non-empty subsequences from the nums
array such that the sum of the smallest and largest number in each subsequence is less than or equal to the target
. Since the answer could be very large, we only require the answer modulo 10^9 + 7
. It's noteworthy to mention that a subsequence does not have to consist of consecutive elements and can be formed by deleting some or no elements without changing the order of the remaining elements.
Intuition
To solve this problem, we should think about certain properties of subsequences and constraints. A critical observation is that for a given smallest element, if we can fix the largest element that would satisfy the target constraint, then all combinations of elements between the smallest and largest one will also satisfy the property (because adding elements in between will not affect the smallest and largest values of the subsequence).
So, the steps we might consider are:
- Sort the array to efficiently manage the smallest and largest elements.
- Initialize an array
f
to precompute the powers of 2, which represent the number of combinations of elements in between two fixed points, since those can freely be included or excluded. - Iterate over the sorted array with a pointer
i
to find a valid smallest element. - For each
i
, use binary search (bisect_right
) to find the largest permissible elementj
wherenums[i] + nums[j]
is still not greater thantarget
. - The power of 2 at
f[j - i]
now tells us the count of valid subsequences betweeni
andj
because all in-between elements give us that many combinations. We use modular arithmetic for this calculation. - We continue until the smallest element alone exceeds half the
target
, since no viable pair (as smallest + largest) will then satisfy the sum constraint. - Sum all these counts to get the answer.
This approach minimizes the computation by reducing the problem to a series of binary searches and combinations (powers of 2) within the sorted bounds of the array, leveraging the property of subsequences in a sorted array.
Learn more about Two Pointers, Binary Search and Sorting patterns.
Solution Approach
The solution primarily makes use of sorting, binary search, pre-computed powers of two, and modular arithmetic. Here is the step-by-step explanation:
-
Sorting: The first step is to sort the
nums
array. Sorting is essential as it allows us to treat the first element of any subsequence we consider as the minimum and the last as the maximum. This makes it simple to enforce the constraint that the sum of the minimum and maximum elements is less than or equal totarget
. -
Precomputing Powers of Two: Before entering the main loop, we initialize an array
f
wheref[i]
is meant to store2^i % mod
. This array is filled up ton
(the length ofnums
) plus one to account for an empty subsequence. The reason for this is that for any fixed pair of minimum and maximum, there are2^(number of elements between them)
possible subsequences including or excluding these middle elements. -
Main Loop: The main loop iterates over each element
x
in the sorted arraynums
. This element is sampled as a candidate for the minimum value in our subsequence. -
Binary Search: For each candidate minimum element, we use
bisect_right
from thebisect
module to efficiently find the rightmost indexj
such that the sum ofnums[i]
andnums[j]
is less than or equal totarget
. The functionbisect_right(nums, target - x, i + 1)
is used to find an index just beyond the largest element that can be paired withnums[i]
to form a valid subsequence. -
Counting Valid Subsequences: After finding
j
, we calculate the number of valid subsequences that havenums[i]
as the smallest andnums[j]
as the largest element. This number isf[j - i]
, which is the count of all subsequences formed by the elements in betweeni
andj
. This value is added to our running totalans
, using modular arithmetic to prevent overflow. -
Modular Arithmetic: All arithmetic operations are done modulo
10^9 + 7
(mod
), as the problem statement requests the final answer to be given modulo this prime number. This ensures that intermediate results and the final answer stay within the bounds of anint
and do not cause overflow. -
Break Condition: We can break early out of our loop when the minimum element itself is greater than half of the
target
. Since the array is sorted and any pair will at least double the minimum value, no subsequent pairs can have a valid sum, optimizing our solution.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's say the nums
array is [1, 2, 3, 4, 5]
, and the target
is 7
. Here's how the solution approach would be applied to this example:
-
Sorting: First, we sort the array, but since it is already sorted
[1, 2, 3, 4, 5]
, there's no change. -
Precomputing Powers of Two: Suppose we precompute powers of two modulo
10^9+7
up ton+1
wheren
is length ofnums
. Our arrayf
for powers of 2 will look like this:[1, 2, 4, 8, 16, ...]
becausef[0] = 2^0 % mod
,f[1] = 2^1 % mod
, and so on. -
Main Loop: We iterate
i
from the start of the array. Starting withi=0
, our minimum candidate value isnums[0] = 1
. -
Binary Search: We perform a binary search to find the border
j
. Usingbisect_right
, we find the largestj
such thatnums[i] + nums[j] <= target
. Fori=0
andtarget=7
, the largest pairable value with1
is5
, soj=4
(index of5
). -
Counting Valid Subsequences: There are
j - i - 1
elements betweennums[i]
andnums[j]
, which means4 - 0 - 1 = 3
elements. Thus, there are2^3 = 8
possible subsequences. After processingi=0
, ourans
is8 % mod
. -
Modular Arithmetic: We continue the loop and perform the same computations. As we continue, all operations are done modulo
10^9 + 7
. -
Break Condition: We reach a point where the smallest element
nums[i]
is greater than half the target. Here, wheni
reaches4
(nums[i]=5
), we can break out of the loop, as no subsequent pairs from the sorted array will satisfy the sum condition. The loop condition saves us from going through unnecessary elements.
In the provided array, we keep picking a smallest element x
(starting from 1
to 5
), and for each x
, we find the maximum y
such that x+y <= target
using binary search. Then, we calculate all possible subsequences using f[j - i]
. Summing these counts gives us the total number of valid subsequences whose sum of smallest and largest numbers is less than or equal to the target
.
By applying this process to the example given, we successfully count all valid subsequences while efficiently managing the constraints through sorting, binary search, and precomputed powers of two, combined with modular arithmetic to keep the numbers manageable.
Solution Implementation
1from bisect import bisect_right
2
3class Solution:
4 def numSubseq(self, nums: List[int], target: int) -> int:
5 # Constant for modulo operation
6 mod = 10**9 + 7
7 # Sort the input list to make use of binary search later
8 nums.sort()
9 n = len(nums)
10
11 # Initialize power_of_two array which stores 2^i values modulo mod
12 power_of_two = [1] * (n + 1)
13 for i in range(1, n + 1):
14 # Efficiently precompute powers of 2 mod mod
15 power_of_two[i] = power_of_two[i - 1] * 2 % mod
16
17 # Initialize the answer to 0
18 ans = 0
19 # Loop through the list
20 for i, num in enumerate(nums):
21 # Stop if the smallest number in a subsequence is too big
22 if num * 2 > target:
23 break
24 # Find the largest number that can be paired with nums[i]
25 # such that their sum does not exceed target.
26 j = bisect_right(nums, target - num, i + 1) - 1
27
28 # Add the count of valid subsequences starting with nums[i]
29 # The count is the number of different ways to form subsequences
30 # from i+1 to j (inclusive), which is simply 2 raised to the power
31 # of the number of elements between i and j, modulo mod.
32 # This relies on the fact that for every element between i and j,
33 # we can choose to either include it or not in our subsequence.
34 ans = (ans + power_of_two[j - i]) % mod
35
36 # Return the total count of valid subsequences modulo mod
37 return ans
38
1class Solution {
2 public int numSubseq(int[] nums, int target) {
3 // Sort the input array to facilitate the two-pointer approach
4 Arrays.sort(nums);
5
6 // Modulus value for avoiding integer overflow
7 final int MOD = (int) 1e9 + 7;
8
9 // Get the length of the nums array
10 int n = nums.length;
11
12 // Create an array to store powers of 2 mod MOD, up to n
13 int[] powersOfTwoMod = new int[n + 1];
14 powersOfTwoMod[0] = 1;
15
16 // Precompute the powers of two modulo MOD for later use
17 for (int i = 1; i <= n; ++i) {
18 powersOfTwoMod[i] = (powersOfTwoMod[i - 1] * 2) % MOD;
19 }
20
21 // Variable to store the final answer
22 int answer = 0;
23
24 // Iterate through the numbers in the sorted array
25 for (int i = 0; i < n; ++i) {
26 // If the smallest number in the subsequence is greater than half of the target, stop the loop
27 if (nums[i] * 2L > target) {
28 break;
29 }
30
31 // Find the largest index j such that nums[i] + nums[j] <= target
32 int j = binarySearch(nums, target - nums[i], i + 1) - 1;
33
34 // Add the count of subsequences using the powers of two precomputed values
35 answer = (answer + powersOfTwoMod[j - i]) % MOD;
36 }
37
38 // Return the total number of subsequences that satisfy the condition
39 return answer;
40 }
41
42 // Helper function: binary search to find the rightmost index where nums[index] <= x
43 private int binarySearch(int[] nums, int x, int left) {
44 int right = nums.length;
45
46 // Continue searching while the search space is valid
47 while (left < right) {
48 int mid = (left + right) >> 1; // Calculate the middle index
49
50 // Narrow the search to the left half if nums[mid] > x
51 if (nums[mid] > x) {
52 right = mid;
53 } else {
54 // Otherwise, narrow the search to the right half
55 left = mid + 1;
56 }
57 }
58
59 // Return the insertion point for x
60 return left;
61 }
62}
63
1class Solution {
2public:
3 int numSubseq(vector<int>& nums, int target) {
4 // Sort the original array to facilitate binary search
5 sort(nums.begin(), nums.end());
6
7 // Define mod as the required modulus
8 const int mod = 1e9 + 7;
9 int n = nums.size();
10
11 // Initialize a vector for fast exponentiation
12 vector<int> fastExp(n + 1);
13 fastExp[0] = 1;
14
15 // Calculate powers of 2 modulo mod in advance
16 for (int i = 1; i <= n; ++i) {
17 fastExp[i] = (fastExp[i - 1] * 2) % mod;
18 }
19
20 int count = 0; // Initialize count of subsequences
21
22 // Iterate over the nums array to find valid subsequences
23 for (int i = 0; i < n; ++i) {
24 // If the smallest number is already greater than the target when doubled, break
25 if (nums[i] * 2L > target) {
26 break;
27 }
28
29 // Find the index of the largest number that can be paired with nums[i]
30 int j = upper_bound(nums.begin() + i + 1, nums.end(), target - nums[i]) - nums.begin() - 1;
31
32 // Add the number of valid subsequences with nums[i] as the smallest number
33 count = (count + fastExp[j - i]) % mod;
34 }
35
36 // Return the total count of valid subsequences
37 return count;
38 }
39};
40
1// Define mod as the required modulus
2const MOD = 1e9 + 7;
3
4// Function for fast exponentiation
5const fastExponentiation = (length: number): number[] => {
6 let fastExp: number[] = new Array(length + 1).fill(1);
7 for (let i = 1; i <= length; ++i) {
8 fastExp[i] = (fastExp[i - 1] * 2) % MOD;
9 }
10 return fastExp;
11};
12
13// Function to count number of subsequences with sum of min + max <= target
14const numSubseq = (nums: number[], target: number): number => {
15 // Sort the original array to facilitate binary search
16 nums.sort((a, b) => a - b);
17
18 const n: number = nums.length;
19 // Initialize vector for fast exponentiation
20 const fastExp = fastExponentiation(n);
21
22 let count = 0; // Initialize count of subsequences
23
24 // Iterate over the nums array to find valid subsequences
25 for (let i = 0; i < n; ++i) {
26 // If the smallest number is already greater than the target when doubled, exit loop
27 if (nums[i] * 2 > target) {
28 break;
29 }
30
31 // Find the index of the largest number that can be paired with nums[i]
32 let j = upperBound(nums, i, n, target - nums[i]) - 1;
33
34 // Add the number of valid subsequences with nums[i] as the smallest number
35 count = (count + fastExp[j - i]) % MOD;
36 }
37
38 // Return the total count of valid subsequences
39 return count;
40};
41
42// Function that works like C++ upper_bound
43// It finds the first index in nums where nums[index] is greater than value
44const upperBound = (nums: number[], startIndex: number, length: number, value: number): number => {
45 let low = startIndex, high = length;
46 while (low < high) {
47 const mid: number = low + Math.floor((high - low) / 2);
48 if (value >= nums[mid]) {
49 low = mid + 1;
50 } else {
51 high = mid;
52 }
53 }
54 return low;
55};
56
Time and Space Complexity
The given Python code aims to count the number of subsequnces in an array nums
that add up to a sum less than or equal to target
, with a constraint that within each subsequence, the maximum plus minimum value should not exceed target
. Here's the analysis of its time complexity and space complexity:
Time Complexity
-
nums.sort()
: This line sorts the array in place which, in the worst case, has a time complexity ofO(n log n)
, wheren
is the length of the array. -
The loop to calculate powers of 2 (
f[i] = f[i - 1] * 2 % mod
) runsn
times, hence the time complexity for this loop isO(n)
. -
The main loop, which calculates the answer, iterates over the array once (
for i, x in enumerate(nums)
), which givesO(n)
complexity for the loop's iteration. -
Inside the loop,
bisect_right
is used, which is an algorithm for binary search in Python, and it has a time complexity ofO(log n)
. However, because it runs once for each element innums
, the overall complexity for this part isO(n log n)
.
The dominating factor in the above analyses is O(n log n)
. The sort
operation and the binary search inside the loop both contribute to this complexity, thus the total time complexity of the function is O(n log n)
.
Space Complexity
-
The space allocated for
f
which stores the increasing powers of 2, up ton
, isO(n)
since it holdsn + 1
elements. -
No additional significant space is used, as the sorting is done in place and the other operations use constant space.
Therefore, the overall space complexity of the function is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
In a binary min heap, the minimum element can be found in:
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Want a Structured Path to Master System Design Too? Donāt Miss This!