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 <= 1050 <= 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 × 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 × 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 × 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 × f[i - 1][0] + 1, \quad nums[i] = 0 \
f[i][1] &= f[i-1][0] + 2 × f[i - 1][1], \quad nums[i] = 1 \
f[i][2] &= f[i-1][1] + 2 × f[i - 1][2], \quad nums[i] = 2 \
f[i][j] &= f[i-1][j], \quad nums[i] ≠ 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
PythonJavaC++GoTypeScript
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](code-box)
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];
}
}(code-box)
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];
}
};(code-box)
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]
}(code-box)
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];
}(code-box)
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.
PythonJavaC++GoTypeScript
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](code-box)
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];
}
}(code-box)
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];
}
};(code-box)
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]
}(code-box)
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];
}(code-box)
