Count Number of Special Subsequences
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating every possible subsequence of the input array nums. For each subsequence generated, a check is performed to determine if it qualifies as a "special" subsequence. A counter is used to tally the total number of such special subsequences found.
Algorithm
- Define a recursive function, say
findSubsequences(index, currentList), to generate all subsequences. - The
indexparameter tracks the current position in thenumsarray, andcurrentListstores the subsequence being built. - Base Case: When
indexreaches the end ofnums, check ifcurrentListis a special subsequence using a helper functionisSpecial(). - If
isSpecial()returns true, increment a global counter (modulo10^9 + 7). - Recursive Step: For each element at
index, make two recursive calls:- One without including
nums[index]incurrentList. - One including
nums[index]incurrentList.
- One without including
- The
isSpecial(list)helper function verifies if a given list follows the0...1...2...pattern with at least one of each number.
Walkthrough
The core of this method is a backtracking algorithm. We can define a recursive function that explores two choices for each element in the input array: either include it in the current subsequence or not. This process branches out, eventually generating all 2^N possible subsequences, where N is the length of nums.
When the recursion reaches the end of the array, we have a complete subsequence. We then pass this subsequence to a validation function, isSpecial(). This function checks if the subsequence adheres to the required structure: a non-empty sequence of 0s, followed by a non-empty sequence of 1s, and finally a non-empty sequence of 2s. If the subsequence is valid, we increment our total count. Because two subsequences are different if their chosen indices are different, this method correctly counts all valid combinations. However, its exponential nature makes it impractical for the given constraints.
Complexity
Time
O(N * 2^N). There are 2^N subsequences to generate. For each subsequence, the `isSpecial()` check can take up to O(N) time.
Space
O(N), where N is the length of `nums`. This is due to the recursion depth and the space required to store the current subsequence being built.
Trade-offs
Pros
Conceptually simple and directly follows the problem's definition of a subsequence.
Easy to implement for someone familiar with recursion and backtracking.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' error on any reasonably sized input.
A more efficient method is to use dynamic programming. We can build the solution iteratively by keeping track of the number of valid subsequences of different types as we scan through the input array. This avoids the redundant calculations inherent in the brute-force approach.
Algorithm
- Create a 2D DP table
dp[n+1][3], wherenis the length ofnums. dp[i][0]will store the count of subsequences usingnums[0...i-1]of the form0....dp[i][1]will store the count of subsequences usingnums[0...i-1]of the form0...1....dp[i][2]will store the count of subsequences usingnums[0...i-1]of the form0...1...2...(special subsequences).- Iterate
ifrom 1 ton. In each iteration, first copy the results from the previous step:dp[i][j] = dp[i-1][j]. - Then, update the counts based on the current number
nums[i-1]:- If
nums[i-1] == 0: Updatedp[i][0] = (dp[i][0] + dp[i-1][0] + 1) % MOD. - If
nums[i-1] == 1: Updatedp[i][1] = (dp[i][1] + dp[i-1][0] + dp[i-1][1]) % MOD. - If
nums[i-1] == 2: Updatedp[i][2] = (dp[i][2] + dp[i-1][1] + dp[i-1][2]) % MOD.
- If
- The final answer is
dp[n][2].
Walkthrough
We define a DP table, dp[i][j], to store counts up to index i-1 of the input array. The second dimension j represents the type of subsequence we are counting:
j=0: Subsequences with only 0s (e.g.,[0],[0,0]).j=1: Subsequences with 0s followed by 1s (e.g.,[0,1],[0,0,1,1]).j=2: Special subsequences with 0s, then 1s, then 2s.
We iterate through nums, and for each element nums[i-1], we calculate dp[i] based on dp[i-1]. The logic is that for each number, we can either not include it (in which case the counts are the same as dp[i-1]) or include it. If we include nums[i-1], it can extend existing subsequences or start new ones, and we update the corresponding count. For example, if we see a 1, it can extend any subsequence of type 0 or type 1. The total count for type 1 subsequences at step i will be the sum of subsequences from i-1 plus the new ones we can form. The final answer is the total count of type 2 subsequences after processing the entire array.
Complexity
Time
O(N), as we iterate through the input array once with constant time operations at each step.
Space
O(N), for the DP table of size `(N+1) x 3`.
Trade-offs
Pros
Provides a correct and efficient polynomial-time solution (O(N)).
The DP state transitions are logical and easy to follow.
Cons
Uses O(N) space, which is not optimal for this problem.
Can be memory-intensive for very large N, although it fits within typical constraints.
This is the most optimal solution. It improves upon the previous DP approach by reducing the space complexity. By observing that the DP calculation at step i only requires the results from step i-1, we can eliminate the need for a full DP table and use only a few variables to store the necessary state.
Algorithm
- Initialize three
longvariables:count0,count1,count2to 0. count0: stores the number of valid subsequences ending in 0.count1: stores the number of valid subsequences ending in 1 (of form0...1...).count2: stores the number of valid special subsequences (of form0...1...2...).- Iterate through each
numin thenumsarray. - Based on the value of
num, update the counts using the following recurrence relations (all operations are modulo10^9 + 7):- If
num == 0:count0 = (2 * count0 + 1). - If
num == 1:count1 = (2 * count1 + count0). - If
num == 2:count2 = (2 * count2 + count1).
- If
- After the loop finishes,
count2will hold the final answer.
Walkthrough
Instead of a 2D array, we use three variables: count0, count1, and count2, to represent the number of subsequences ending in 0, 1, and 2, respectively, that satisfy the special sequence prefix rules. We iterate through the input array nums once.
- When we encounter a
0: Any new subsequence ending with this0can be formed by either appending it to an existing subsequence of0s (doubling the possibilities, hence2 * count0) or by starting a new subsequence with this single0(adding 1). So,count0becomes(2 * count0 + 1) % MOD. - When we encounter a
1: A new subsequence ending with this1can be formed by appending it to any subsequence ending in0(count0ways) or any subsequence ending in1(count1ways). The total count becomescount1(old ones) +count0+count1(new ones), which simplifies tocount1 = (2 * count1 + count0) % MOD. - When we encounter a
2: Following the same logic, a new subsequence ending in2can be formed by appending it to any subsequence ending in1(count1ways) or2(count2ways). Thus,count2 = (2 * count2 + count1) % MOD.
After iterating through all numbers, count2 contains the total count of special subsequences.
Complexity
Time
O(N), as it involves a single pass through the input array.
Space
O(1), as we only use a constant number of variables to maintain the counts.
Trade-offs
Pros
Optimal time complexity of O(N).
Optimal space complexity of O(1).
Highly efficient and scalable for large inputs.
Cons
The logic for the state transitions, while concise, might be slightly less intuitive to derive compared to the table-based approach.
Solutions
Solution
class Solution {public int countSpecialSubsequences(int[] nums) { final int mod = (int)1 e9 + 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]; }}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]; }};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]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.