#2977Time: O(2^N * N). There are 2^N possible subsequences. For each subsequence of length k, it takes O(k) to check if it's good and to sum its elements. In the worst case, this leads to an exponential time complexity.Space: O(N), where N is the length of `nums`. This space is used by the recursion call stack. The depth of the recursion can go up to N.
You are given an integer array nums. A good subsequence is defined as a subsequence of nums where the absolute difference between any two consecutive elements in the subsequence is exactly 1.
Return the sum of all possiblegood subsequences of nums.
Since the answer may be very large, return it modulo109 + 7.
Note that a subsequence of size 1 is considered good by definition.
Example 1:
Input:nums = [1,2,1]
Output:14
Explanation:
Good subsequences are: [1], [2], [1], [1,2], [2,1], [1,2,1].
The sum of elements in these subsequences is 14.
Example 2:
Input:nums = [3,4,5]
Output:40
Explanation:
Good subsequences are: [3], [4], [5], [3,4], [4,5], [3,4,5].
The sum of elements in these subsequences is 40.
Constraints:
1 <= nums.length <= 105
0 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward, yet inefficient, way to solve this problem is to generate all possible subsequences of the input array nums. For each generated subsequence, we check if it meets the criteria of a 'good' subsequence. If it does, we calculate the sum of its elements and add it to a global total. This can be implemented using recursion or iteration to generate the power set of nums.
Algorithm
Define a recursive function, say solve(index, currentSubsequence).
The base case for the recursion is when index reaches the end of the nums array.
In the recursive step, for each element nums[index], we have two choices:
Include nums[index]: Check if adding nums[index] to currentSubsequence maintains the 'good' property. This is true if currentSubsequence is empty or abs(nums[index] - last_element_of_subsequence) == 1.
If it's valid to include nums[index], form a new subsequence, add its sum to a running total, and make a recursive call solve(index + 1, newSubsequence).
This method explores all 2^N subsequences, checks each for the 'good' property, and sums them up if they are.
Walkthrough
This approach uses a classic backtracking algorithm to explore every possible subsequence. We can define a recursive function that builds a subsequence element by element. At each step, we decide whether to include the current element from the nums array into the subsequence we are building.
When we consider including an element, we must first verify that it preserves the 'good' subsequence property. A number can be appended to the current subsequence only if the subsequence is empty or if the absolute difference between the number and the last element of the subsequence is exactly 1. If the condition is met, we add the number, add the new subsequence's sum to our total answer, and recurse further. If not, we backtrack and explore other possibilities.
While this correctly finds all good subsequences, its performance is very poor. The total number of subsequences is 2^N, where N is the length of nums. For each subsequence, we perform a check and a sum, leading to a time complexity that is exponential, making it infeasible for the problem's constraints.
Complexity
Time
O(2^N * N). There are 2^N possible subsequences. For each subsequence of length k, it takes O(k) to check if it's good and to sum its elements. In the worst case, this leads to an exponential time complexity.
Space
O(N), where N is the length of `nums`. This space is used by the recursion call stack. The depth of the recursion can go up to N.
Trade-offs
Pros
Conceptually simple and easy to understand.
A direct translation of the problem statement into code.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
Generates and checks many subsequences that are not 'good', leading to wasted computation.
A better approach involves dynamic programming. We can build the solution based on subproblems. Let dp[i] be the sum of all good subsequences that end with the element at index i. To compute dp[i], we can iterate through all previous elements nums[j] (where j < i) and, if nums[i] can extend a good subsequence ending at nums[j], we add the contribution to dp[i]. We also need to keep track of the count of such subsequences.
Algorithm
Initialize two arrays, dp and count, of size N (the length of nums).
dp[i] will store the sum of all good subsequences ending with nums[i].
count[i] will store the number of good subsequences ending with nums[i].
Initialize a variable totalSum = 0.
Iterate through nums with an index i from 0 to N-1.
For each i, initialize dp[i] = nums[i] and count[i] = 1 to account for the subsequence [nums[i]].
Start an inner loop with index j from 0 to i-1.
If abs(nums[i] - nums[j]) == 1, it means we can extend the good subsequences ending at j.
Update dp[i] by adding the sum of these newly formed subsequences: dp[i] += dp[j] + count[j] * nums[i].
Update count[i] by adding the count of subsequences from j: count[i] += count[j].
After the inner loop, add dp[i] to totalSum.
Return totalSum modulo 10^9 + 7.
Walkthrough
This method uses dynamic programming based on the indices of the array. We create two arrays, dp and count, of the same size as nums.
dp[i]: Stores the cumulative sum of all good subsequences that end with the element nums[i].
count[i]: Stores the total number of good subsequences that end with nums[i].
We iterate from i = 0 to n-1. For each element nums[i], we first consider it as a subsequence of length one. So, we initialize dp[i] = nums[i] and count[i] = 1. Then, we iterate through all previous elements nums[j] where j < i. If abs(nums[i] - nums[j]) == 1, it means we can append nums[i] to any good subsequence that ended at j. The sum of these new subsequences is the sum of the old subsequences (dp[j]) plus nums[i] added for each old subsequence (count[j] * nums[i]). We add this to dp[i] and update count[i] by adding count[j]. The final answer is the sum of all dp[i] values.
1class Solution {2 public int sumOfGoodSubsequences(int[] nums) {3 int n = nums.length;4 long MOD = 1_000_000_007;5 long[] dp = new long[n];6 long[] count = new long[n];7 long totalSum = 0;89 for (int i = 0; i < n; i++) {10 dp[i] = nums[i];11 count[i] = 1;12 for (int j = 0; j < i; j++) {13 if (Math.abs(nums[i] - nums[j]) == 1) {14 dp[i] = (dp[i] + dp[j] + (count[j] * nums[i])) % MOD;15 count[i] = (count[i] + count[j]) % MOD;16 }17 }18 totalSum = (totalSum + dp[i]) % MOD;19 }20 return (int) totalSum;21 }22}
Complexity
Time
O(N^2) due to the nested loops required to check every previous element for each element in `nums`.
Space
O(N) to store the `dp` and `count` arrays.
Trade-offs
Pros
Significant improvement over the brute-force approach.
Correctly utilizes the overlapping subproblems property of dynamic programming.
Cons
The O(N^2) time complexity is too slow for the given constraints (N up to 10^5), and will time out.
The O(N^2) DP approach can be optimized to O(N). The inner loop in the previous approach is inefficient because it re-scans all previous elements. We can observe that to compute the state for a number num, we only need the aggregated information for numbers num-1 and num+1. We can maintain this information in an array or a hash map, where the key is the number's value, allowing for O(1) lookups.
Algorithm
Initialize two arrays (or hash maps), sumEndingWith and countEndingWith, to store the DP states. The size should be based on the maximum possible value in nums.
Initialize totalSum = 0 and MOD = 10^9 + 7.
Iterate through each num in the input array nums.
For the current num, retrieve the total sum and count of good subsequences ending in num - 1 and num + 1 from the DP arrays.
Calculate currentSum, the sum of all good subsequences ending with the currentnum. This is num (for the subsequence [num]) plus the sums from extending subsequences ending in num-1 and num+1.
The formula is:
1currentSum = (num + sumEndingWith[num-1] + countEndingWith[num-1] * num + sumEndingWith[num+1] + countEndingWith[num+1] * num) % MOD
.
Calculate currentCount, the number of such subsequences: currentCount = (1 + countEndingWith[num-1] + countEndingWith[num+1]) % MOD.
Add currentSum to the totalSum.
Update the DP state for value num: sumEndingWith[num] += currentSum and countEndingWith[num] += currentCount.
Return the final totalSum.
Walkthrough
This optimal approach uses dynamic programming where the state is based on the value of the elements, not their indices. We use two arrays, sumEndingWith and countEndingWith, to store the running totals.
sumEndingWith[v]: The sum of all good subsequences encountered so far that end with the value v.
countEndingWith[v]: The count of all good subsequences encountered so far that end with the value v.
We iterate through nums once. For each number num, we calculate the sum and count of new good subsequences that end with this specific num. These can be formed in three ways:
A new subsequence of size one: [num]. Its sum is num and count is 1.
By extending all existing good subsequences that end with num - 1.
By extending all existing good subsequences that end with num + 1.
The total sum for subsequences ending at the current num is the sum of contributions from these three sources. We can get the required information for num-1 and num+1 directly from our DP arrays in O(1) time. After calculating the sum (currentSum) for the current num, we add it to our overall totalSum and update the DP arrays sumEndingWith[num] and countEndingWith[num] for future elements to use.
Since nums[i] is bounded by 10^5, arrays are a suitable choice for storing the DP states.
1class Solution {2 public int sumOfGoodSubsequences(int[] nums) {3 int MOD = 1_000_000_007;4 int maxVal = 0;5 for (int num : nums) {6 maxVal = Math.max(maxVal, num);7 }89 // We need to access num+1, so size should be maxVal + 210 long[] sumEndingWith = new long[maxVal + 2];11 long[] countEndingWith = new long[maxVal + 2];12 long totalSum = 0;1314 for (int num : nums) {15 long sumPrevMinus1 = (num > 0) ? sumEndingWith[num - 1] : 0;16 long countPrevMinus1 = (num > 0) ? countEndingWith[num - 1] : 0;1718 long sumPrevPlus1 = sumEndingWith[num + 1];19 long countPrevPlus1 = countEndingWith[num + 1];2021 long term1 = (countPrevMinus1 * num) % MOD;22 long term2 = (countPrevPlus1 * num) % MOD;2324 long currentSum = (num + sumPrevMinus1 + term1 + sumPrevPlus1 + term2) % MOD;25 long currentCount = (1 + countPrevMinus1 + countPrevPlus1) % MOD;2627 totalSum = (totalSum + currentSum) % MOD;2829 sumEndingWith[num] = (sumEndingWith[num] + currentSum) % MOD;30 countEndingWith[num] = (countEndingWith[num] + currentCount) % MOD;31 }3233 return (int) totalSum;34 }35}
Complexity
Time
O(N), where N is the length of `nums`. We iterate through the array once, and all operations inside the loop are constant time.
Space
O(M), where M is the maximum value in `nums`. This is for the DP arrays. Given `M <= 10^5`, this is efficient.
Trade-offs
Pros
Optimal time complexity, making it very efficient for the given constraints.
Single pass through the input array.
Cons
Requires extra space proportional to the range of values in the input array, which could be large if the values are not bounded.
Solutions
Solution
1class Solution {2public3 int sumOfGoodSubsequences(int[] nums) {4 final int mod = (int)1 e9 + 7;5 int mx = 0;6 for (int x : nums) {7 mx = Math.max(mx, x);8 }9 long[] f = new long[mx + 1];10 long[] g = new long[mx + 1];11 for (int x : nums) {12 f[x] += x;13 g[x] += 1;14 if (x > 0) {15 f[x] = (f[x] + f[x - 1] + g[x - 1] * x % mod) % mod;16 g[x] = (g[x] + g[x - 1]) % mod;17 }18 if (x + 1 <= mx) {19 f[x] = (f[x] + f[x + 1] + g[x + 1] * x % mod) % mod;20 g[x] = (g[x] + g[x + 1]) % mod;21 }22 }23 long ans = 0;24 for (long x : f) {25 ans = (ans + x) % mod;26 }27 return (int)ans;28 }29}
