Problem

A sequence is special if it consists of a positive number of 0s, followed by a positive number of 1s, then a positive number of 2s.

  • For example, [0,1,2] and [0,0,1,1,1,2] are special.
  • In contrast, [2,1,0], [1], and [0,1,2,0] are not special.

Given an array nums (consisting of only integers 0, 1, and 2), return thenumber of different subsequences that are special. Since the answer may be very large, return it modulo10^9 + 7.

A subsequence of an array is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. Two subsequences are different if the set of indices chosen are different.

Examples

Example 1

1
2
3

Input: nums = [0,1,2,2]
Output: 3
Explanation: The special subsequences are bolded [**_0_** ,**_1_** ,**_2_** ,2], [**_0_** ,**_1_** ,2,**_2_**], and [**_0_** ,**_1_** ,**_2_** ,**_2_**].

Example 2

1
2
3

Input: nums = [2,2,0,0]
Output: 0
Explanation: There are no special subsequences in [2,2,0,0].

Example 3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

Input: nums = [0,1,2,0,1,2]
Output: 7
Explanation: The special subsequences are bolded:
- [**_0_** ,**_1_** ,**_2_** ,0,1,2]
- [**_0_** ,**_1_** ,2,0,1,**_2_**]
- [**_0_** ,**_1_** ,**_2_** ,0,1,**_2_**]
- [**_0_** ,**_1_** ,2,0,**_1_** ,**_2_**]
- [**_0_** ,1,2,**_0_** ,**_1_** ,**_2_**]
- [**_0_** ,1,2,0,**_1_** ,**_2_**]
- [0,1,2,**_0_** ,**_1_** ,**_2_**]

Constraints

  • 1 <= nums.length <= 10^5
  • 0 <= nums[i] <= 2

Solution

Method 1 – Dynamic Programming (Counting Subsequences by State)

Intuition

We can use dynamic programming to count the number of special subsequences ending with 0, 1, and 2. For each number, we update the count of subsequences that can be formed by including or excluding the current number, maintaining the required order.

Approach

  1. Initialize three counters: cnt0 for subsequences ending with 0, cnt1 for those ending with 1, and cnt2 for those ending with 2.
  2. Iterate through the array:
    • If the number is 0: it can start a new subsequence or extend existing ones ending with 0.
    • If the number is 1: it can extend subsequences ending with 0 or extend existing ones ending with 1.
    • If the number is 2: it can extend subsequences ending with 1 or extend existing ones ending with 2.
  3. The answer is the total number of subsequences ending with 2.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        const int MOD = 1e9+7;
        long long cnt0 = 0, cnt1 = 0, cnt2 = 0;
        for (int x : nums) {
            if (x == 0) cnt0 = (2 * cnt0 + 1) % MOD;
            else if (x == 1) cnt1 = (2 * cnt1 + cnt0) % MOD;
            else cnt2 = (2 * cnt2 + cnt1) % MOD;
        }
        return cnt2;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func CountSpecialSubsequences(nums []int) int {
    const MOD = 1_000_000_007
    cnt0, cnt1, cnt2 := 0, 0, 0
    for _, x := range nums {
        if x == 0 {
            cnt0 = (2*cnt0 + 1) % MOD
        } else if x == 1 {
            cnt1 = (2*cnt1 + cnt0) % MOD
        } else {
            cnt2 = (2*cnt2 + cnt1) % MOD
        }
    }
    return cnt2
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int countSpecialSubsequences(int[] nums) {
        int MOD = 1_000_000_007;
        long cnt0 = 0, cnt1 = 0, cnt2 = 0;
        for (int x : nums) {
            if (x == 0) cnt0 = (2 * cnt0 + 1) % MOD;
            else if (x == 1) cnt1 = (2 * cnt1 + cnt0) % MOD;
            else cnt2 = (2 * cnt2 + cnt1) % MOD;
        }
        return (int)cnt2;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    fun countSpecialSubsequences(nums: IntArray): Int {
        val MOD = 1_000_000_007
        var cnt0 = 0L; var cnt1 = 0L; var cnt2 = 0L
        for (x in nums) {
            when (x) {
                0 -> cnt0 = (2 * cnt0 + 1) % MOD
                1 -> cnt1 = (2 * cnt1 + cnt0) % MOD
                2 -> cnt2 = (2 * cnt2 + cnt1) % MOD
            }
        }
        return cnt2.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def countSpecialSubsequences(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        cnt0 = cnt1 = cnt2 = 0
        for x in nums:
            if x == 0:
                cnt0 = (2 * cnt0 + 1) % MOD
            elif x == 1:
                cnt1 = (2 * cnt1 + cnt0) % MOD
            else:
                cnt2 = (2 * cnt2 + cnt1) % MOD
        return cnt2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn count_special_subsequences(nums: Vec<i32>) -> i32 {
        let m = 1_000_000_007;
        let (mut cnt0, mut cnt1, mut cnt2) = (0, 0, 0);
        for x in nums {
            if x == 0 {
                cnt0 = (2 * cnt0 + 1) % m;
            } else if x == 1 {
                cnt1 = (2 * cnt1 + cnt0) % m;
            } else {
                cnt2 = (2 * cnt2 + cnt1) % m;
            }
        }
        cnt2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    countSpecialSubsequences(nums: number[]): number {
        const MOD = 1_000_000_007;
        let cnt0 = 0, cnt1 = 0, cnt2 = 0;
        for (const x of nums) {
            if (x === 0) cnt0 = (2 * cnt0 + 1) % MOD;
            else if (x === 1) cnt1 = (2 * cnt1 + cnt0) % MOD;
            else cnt2 = (2 * cnt2 + cnt1) % MOD;
        }
        return cnt2;
    }
}

Complexity

  • ⏰ Time complexity: O(n) – We process each element once, updating three counters.
  • 🧺 Space complexity: O(1) – Only a few variables are used for counting.