Skip to content

1955. Count Number of Special Subsequences

Description

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 the number of different subsequences that are special. Since the answer may be very large, return it modulo 109 + 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.

 

Example 1:

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:

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

Example 3:

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 <= 105
  • 0 <= nums[i] <= 2

Solutions

Solution 1: Dynamic Programming

We define \(f[i][j]\) to represent the number of special subsequences ending with \(j\) among the first \(i+1\) elements. Initially, \(f[i][j]=0\), and if \(nums[0]=0\), then \(f[0][0]=1\).

For \(i \gt 0\), we consider the value of \(nums[i]\):

If \(nums[i] = 0\): If we do not choose \(nums[i]\), then \(f[i][0] = f[i-1][0]\); if we choose \(nums[i]\), then \(f[i][0]=f[i-1][0]+1\), because we can add a \(0\) to the end of any special subsequence ending with \(0\) to get a new special subsequence, or we can use \(nums[i]\) alone as a special subsequence. Therefore, \(f[i][0] = 2 \times f[i - 1][0] + 1\). The rest of \(f[i][j]\) is equal to \(f[i-1][j]\).

If \(nums[i] = 1\): If we do not choose \(nums[i]\), then \(f[i][1] = f[i-1][1]\); if we choose \(nums[i]\), then \(f[i][1]=f[i-1][1]+f[i-1][0]\), because we can add a \(1\) to the end of any special subsequence ending with \(0\) or \(1\) to get a new special subsequence. Therefore, \(f[i][1] = f[i-1][0] + 2 \times f[i - 1][1]\). The rest of \(f[i][j]\) is equal to \(f[i-1][j]\).

If \(nums[i] = 2\): If we do not choose \(nums[i]\), then \(f[i][2] = f[i-1][2]\); if we choose \(nums[i]\), then \(f[i][2]=f[i-1][2]+f[i-1][1]\), because we can add a \(2\) to the end of any special subsequence ending with \(1\) or \(2\) to get a new special subsequence. Therefore, \(f[i][2] = f[i-1][1] + 2 \times f[i - 1][2]\). The rest of \(f[i][j]\) is equal to \(f[i-1][j]\).

In summary, we can get the following state transition equations:

\[ \begin{aligned} f[i][0] &= 2 \times f[i - 1][0] + 1, \quad nums[i] = 0 \\ f[i][1] &= f[i-1][0] + 2 \times f[i - 1][1], \quad nums[i] = 1 \\ f[i][2] &= f[i-1][1] + 2 \times f[i - 1][2], \quad nums[i] = 2 \\ f[i][j] &= f[i-1][j], \quad nums[i] \neq j \end{aligned} \]

The final answer is \(f[n-1][2]\).

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Where \(n\) is the length of the array \(nums\).

Similar code found with 1 license type

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        f = [[0] * 3 for _ in range(n)]
        f[0][0] = nums[0] == 0
        for i in range(1, n):
            if nums[i] == 0:
                f[i][0] = (2 * f[i - 1][0] + 1) % mod
                f[i][1] = f[i - 1][1]
                f[i][2] = f[i - 1][2]
            elif nums[i] == 1:
                f[i][0] = f[i - 1][0]
                f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1]) % mod
                f[i][2] = f[i - 1][2]
            else:
                f[i][0] = f[i - 1][0]
                f[i][1] = f[i - 1][1]
                f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2]) % mod
        return f[n - 1][2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countSpecialSubsequences(int[] nums) {
        final int mod = (int) 1e9 + 7;
        int n = nums.length;
        int[][] f = new int[n][3];
        f[0][0] = nums[0] == 0 ? 1 : 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == 0) {
                f[i][0] = (2 * f[i - 1][0] % mod + 1) % mod;
                f[i][1] = f[i - 1][1];
                f[i][2] = f[i - 1][2];
            } else if (nums[i] == 1) {
                f[i][0] = f[i - 1][0];
                f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1] % mod) % mod;
                f[i][2] = f[i - 1][2];
            } else {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1];
                f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2] % mod) % mod;
            }
        }
        return f[n - 1][2];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        const int mod = 1e9 + 7;
        int n = nums.size();
        int f[n][3];
        memset(f, 0, sizeof(f));
        f[0][0] = nums[0] == 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == 0) {
                f[i][0] = (2 * f[i - 1][0] % mod + 1) % mod;
                f[i][1] = f[i - 1][1];
                f[i][2] = f[i - 1][2];
            } else if (nums[i] == 1) {
                f[i][0] = f[i - 1][0];
                f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1] % mod) % mod;
                f[i][2] = f[i - 1][2];
            } else {
                f[i][0] = f[i - 1][0];
                f[i][1] = f[i - 1][1];
                f[i][2] = (f[i - 1][1] + 2 * f[i - 1][2] % mod) % mod;
            }
        }
        return f[n - 1][2];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func countSpecialSubsequences(nums []int) int {
    const mod = 1e9 + 7
    n := len(nums)
    f := make([][3]int, n)
    if nums[0] == 0 {
        f[0][0] = 1
    }
    for i := 1; i < n; i++ {
        if nums[i] == 0 {
            f[i][0] = (2*f[i-1][0] + 1) % mod
            f[i][1] = f[i-1][1]
            f[i][2] = f[i-1][2]
        } else if nums[i] == 1 {
            f[i][0] = f[i-1][0]
            f[i][1] = (f[i-1][0] + 2*f[i-1][1]) % mod
            f[i][2] = f[i-1][2]
        } else {
            f[i][0] = f[i-1][0]
            f[i][1] = f[i-1][1]
            f[i][2] = (f[i-1][1] + 2*f[i-1][2]) % mod
        }
    }
    return f[n-1][2]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function countSpecialSubsequences(nums: number[]): number {
    const mod = 1e9 + 7;
    const n = nums.length;
    const f: number[][] = Array(n)
        .fill(0)
        .map(() => Array(3).fill(0));
    f[0][0] = nums[0] === 0 ? 1 : 0;
    for (let i = 1; i < n; ++i) {
        if (nums[i] === 0) {
            f[i][0] = (((2 * f[i - 1][0]) % mod) + 1) % mod;
            f[i][1] = f[i - 1][1];
            f[i][2] = f[i - 1][2];
        } else if (nums[i] === 1) {
            f[i][0] = f[i - 1][0];
            f[i][1] = (f[i - 1][0] + ((2 * f[i - 1][1]) % mod)) % mod;
            f[i][2] = f[i - 1][2];
        } else {
            f[i][0] = f[i - 1][0];
            f[i][1] = f[i - 1][1];
            f[i][2] = (f[i - 1][1] + ((2 * f[i - 1][2]) % mod)) % mod;
        }
    }
    return f[n - 1][2];
}

Solution 2: Dynamic Programming (Space Optimization)

We notice that in the above state transition equations, the value of \(f[i][j]\) is only related to \(f[i-1][j]\). Therefore, we can remove the first dimension and optimize the space complexity to \(O(1)\).

We can use an array \(f\) of length 3 to represent the number of special subsequences ending with 0, 1, and 2, respectively. For each element in the array, we update the array \(f\) according to the value of the current element.

The time complexity is \(O(n)\), and the space complexity is \(O(1)\). Where \(n\) is the length of the array \(nums\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        f = [0] * 3
        f[0] = nums[0] == 0
        for i in range(1, n):
            if nums[i] == 0:
                f[0] = (2 * f[0] + 1) % mod
            elif nums[i] == 1:
                f[1] = (f[0] + 2 * f[1]) % mod
            else:
                f[2] = (f[1] + 2 * f[2]) % mod
        return f[2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
    public int countSpecialSubsequences(int[] nums) {
        final int mod = (int) 1e9 + 7;
        int n = nums.length;
        int[] f = new int[3];
        f[0] = nums[0] == 0 ? 1 : 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == 0) {
                f[0] = (2 * f[0] % mod + 1) % mod;
            } else if (nums[i] == 1) {
                f[1] = (f[0] + 2 * f[1] % mod) % mod;
            } else {
                f[2] = (f[1] + 2 * f[2] % mod) % mod;
            }
        }
        return f[2];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int countSpecialSubsequences(vector<int>& nums) {
        const int mod = 1e9 + 7;
        int n = nums.size();
        int f[3]{0};
        f[0] = nums[0] == 0;
        for (int i = 1; i < n; ++i) {
            if (nums[i] == 0) {
                f[0] = (2 * f[0] % mod + 1) % mod;
            } else if (nums[i] == 1) {
                f[1] = (f[0] + 2 * f[1] % mod) % mod;
            } else {
                f[2] = (f[1] + 2 * f[2] % mod) % mod;
            }
        }
        return f[2];
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func countSpecialSubsequences(nums []int) int {
    const mod = 1e9 + 7
    n := len(nums)
    f := [3]int{}
    if nums[0] == 0 {
        f[0] = 1
    }
    for i := 1; i < n; i++ {
        if nums[i] == 0 {
            f[0] = (2*f[0] + 1) % mod
        } else if nums[i] == 1 {
            f[1] = (f[0] + 2*f[1]) % mod
        } else {
            f[2] = (f[1] + 2*f[2]) % mod
        }
    }
    return f[2]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function countSpecialSubsequences(nums: number[]): number {
    const mod = 1e9 + 7;
    const n = nums.length;
    const f: number[] = [0, 0, 0];
    f[0] = nums[0] === 0 ? 1 : 0;
    for (let i = 1; i < n; ++i) {
        if (nums[i] === 0) {
            f[0] = (((2 * f[0]) % mod) + 1) % mod;
            f[1] = f[1];
            f[2] = f[2];
        } else if (nums[i] === 1) {
            f[0] = f[0];
            f[1] = (f[0] + ((2 * f[1]) % mod)) % mod;
            f[2] = f[2];
        } else {
            f[0] = f[0];
            f[1] = f[1];
            f[2] = (f[1] + ((2 * f[2]) % mod)) % mod;
        }
    }
    return f[2];
}

Comments