3351. Sum of Good Subsequences LeetCode Solution

In this guide, you will get 3351. Sum of Good Subsequences LeetCode Solution with the best time and space complexity. The solution to Sum of Good Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sum of Good Subsequences solution in C++
Sum of Good Subsequences solution in Java
Sum of Good Subsequences solution in Python
Additional Resources

3351. Sum of Good Subsequences LeetCode Solution image

Problem Statement of Sum of Good Subsequences

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 possible good subsequences of nums.
Since the answer may be very large, return it modulo 109 + 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

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

3351. Sum of Good Subsequences LeetCode Solution in C++

class Solution {
 public:
  int sumOfGoodSubsequences(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int maxNum = ranges::max(nums);
    // endsIn[i] := the number of good subsequences ending in i
    vector<long> endsIn(maxNum + 3);
    // dp[i] := the sum of good subsequences ending in i
    vector<long> dp(maxNum + 3);

    for (const int num : nums) {
      const long seqsToAppend = 1 + endsIn[num] + endsIn[num + 2];
      dp[num + 1] =
          (seqsToAppend * num + (dp[num + 1] + dp[num] + dp[num + 2])) % kMod;
      endsIn[num + 1] = (endsIn[num + 1] + seqsToAppend) % kMod;
    }

    return accumulate(dp.begin(), dp.end(), 0, [&](int subtotal, int d) {
      return (subtotal + d) % kMod;
    });
  }
};
/* code provided by PROGIEZ */

3351. Sum of Good Subsequences LeetCode Solution in Java

class Solution {
  public int sumOfGoodSubsequences(int[] nums) {
    final int kMod = 1000000007;
    final int maxNum = Arrays.stream(nums).max().getAsInt();
    // endsIn[i] := the number of good subsequences ending in i
    long[] endsIn = new long[maxNum + 3];
    // dp[i] := the sum of good subsequences ending in i
    long[] dp = new long[maxNum + 3];

    for (final int num : nums) {
      final long seqsToAppend = 1 + endsIn[num] + endsIn[num + 2];
      dp[num + 1] = (seqsToAppend * num + (dp[num + 1] + dp[num] + dp[num + 2])) % kMod;
      endsIn[num + 1] = (endsIn[num + 1] + seqsToAppend) % kMod;
    }

    int ans = 0;
    for (final long d : dp)
      ans = (int) (ans + d) % kMod;
    return ans;
  }
}
// code provided by PROGIEZ

3351. Sum of Good Subsequences LeetCode Solution in Python

class Solution:
  def sumOfGoodSubsequences(self, nums: list[int]) -> int:
    kMod = 10**9 + 7
    maxNum = max(nums)
    # endsIn[i] := the number of good subsequences ending in i
    endsIn = [0] * (maxNum + 2)
    # dp[i] := the sum of good subsequences ending in i
    dp = [0] * (maxNum + 2)

    for num in nums:
      seqsToAppend = 1 + endsIn[num - 1] + endsIn[num + 1]
      dp[num] = (seqsToAppend * num +
                 (dp[num] + dp[num - 1] + dp[num + 1])) % kMod
      endsIn[num] += seqsToAppend % kMod

    return sum(dp) % kMod
 # code by PROGIEZ