Problem Description

You are given an array nums consisting only of integers 0, 1, and 2.
A special subsequence is a sequence of indices (i1, i2, ..., ik) such that:

• For all j in 1 ≤ j ≤ k, nums[ij] is in non-decreasing order.
• The subsequence contains at least one 0, followed by at least one 1, followed by at least one 2 (in that order, not necessarily consecutively).

Constraints:

• 1 ≤ nums.length ≤ 10^5
• nums[i] is 0, 1, or 2

Thought Process

At first glance, it may seem like we can generate all possible subsequences and count those that fit the pattern. However, with up to 10⁵ elements, this brute-force approach is computationally infeasible.

Instead, we should look for a way to incrementally build up the count of valid subsequences as we process each element. This is reminiscent of dynamic programming, where we track partial results and use them to efficiently build the answer.

For each element in nums, we want to know:

• How many ways are there to build a subsequence ending with 0?
• How many ways to build a valid "0...1" subsequence?
• How many ways to build a valid "0...1...2" subsequence?

Solution Approach

We'll use three counters:

• count0: Number of subsequences ending with 0 (at least one 0)
• count1: Number of subsequences with at least one 0 followed by at least one 1
• count2: Number of subsequences with at least one 0, then at least one 1, then at least one 2 (i.e., special subsequences)

1. Initialize all counters to 0.
2. Iterate through nums:
   • If the current number is 0, every existing 0-subsequence can be extended with this 0, plus we can start a new subsequence with this 0. So, count0 = count0 * 2 + 1.
   • If the current number is 1, every existing 1-subsequence can be extended, and every 0-subsequence can be extended with this 1 to form a new 1-subsequence. So, count1 = count1 * 2 + count0.
   • If the current number is 2, every existing 2-subsequence can be extended, and every 1-subsequence can be extended with this 2 to form a new 2-subsequence. So, count2 = count2 * 2 + count1.
3. Take modulo 10^9 + 7 at each step to avoid overflow.
4. Return count2 as the answer.

This approach ensures we count all valid subsequences efficiently, leveraging dynamic programming principles.

Example Walkthrough

Let's consider nums = [0,1,2,2].
We'll track count0, count1, and count2 as we process each number:

• Start: count0=0, count1=0, count2=0
• i=0, num=0: count0 = 0*2 + 1 = 1
• i=1, num=1: count1 = 0*2 + 1 = 1
• i=2, num=2: count2 = 0*2 + 1 = 1
• i=3, num=2: count2 = 1*2 + 1 = 3

So, the answer is 3.

The three special subsequences are:

1. [0,1,2] (indices 0,1,2)
2. [0,1,2] (indices 0,1,3)
3. [0,1,2,2] (indices 0,1,2,3)

Time and Space Complexity

Brute-force: Generating all subsequences is O(2^n), which is not feasible for n up to 10⁵.

Optimized approach: We process each element once and do constant work per element. Thus, time complexity is O(n).

Space complexity: We only use three integer counters, so space is O(1).

Summary

By recognizing the layered structure of special subsequences (0s, then 1s, then 2s), we avoid brute-force enumeration and instead use dynamic programming with three counters. This reduces the problem to a simple one-pass solution that is both elegant and efficient.

Code Implementation

class Solution:
    def countSpecialSubsequences(self, nums):
        MOD = 10**9 + 7
        count0 = count1 = count2 = 0
        for num in nums:
            if num == 0:
                count0 = (count0 * 2 + 1) % MOD
            elif num == 1:
                count1 = (count1 * 2 + count0) % MOD
            elif num == 2:
                count2 = (count2 * 2 + count1) % MOD
        return count2
      

class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        const int MOD = 1e9 + 7;
        long count0 = 0, count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == 0) {
                count0 = (count0 * 2 + 1) % MOD;
            } else if (num == 1) {
                count1 = (count1 * 2 + count0) % MOD;
            } else if (num == 2) {
                count2 = (count2 * 2 + count1) % MOD;
            }
        }
        return (int)count2;
    }
};
      

class Solution {
    public int countSpecialSubsequences(int[] nums) {
        int MOD = 1_000_000_007;
        long count0 = 0, count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == 0) {
                count0 = (count0 * 2 + 1) % MOD;
            } else if (num == 1) {
                count1 = (count1 * 2 + count0) % MOD;
            } else if (num == 2) {
                count2 = (count2 * 2 + count1) % MOD;
            }
        }
        return (int)count2;
    }
}
      

var countSpecialSubsequences = function(nums) {
    const MOD = 1e9 + 7;
    let count0 = 0, count1 = 0, count2 = 0;
    for (let num of nums) {
        if (num === 0) {
            count0 = (count0 * 2 + 1) % MOD;
        } else if (num === 1) {
            count1 = (count1 * 2 + count0) % MOD;
        } else if (num === 2) {
            count2 = (count2 * 2 + count1) % MOD;
        }
    }
    return count2;
};