Count Number of Special Subsequences - Solution & Explanation
Problem Statement
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
Approach Overview
Problem Overview: Given an array containing only 0, 1, and 2, count subsequences that follow the pattern: one or more 0s, followed by one or more 1s, followed by one or more 2s. The order must be preserved but elements do not need to be contiguous.
Approach 1: Dynamic Programming with State Counts (O(n) time, O(1) space)
Track three running counts while iterating through the array. count0 represents subsequences containing only 0s. count01 represents subsequences that started with 0s and now include 1s. count012 represents complete special subsequences that include 0, 1, and 2. When you encounter a value, update the corresponding state using transitions: a 0 doubles existing count0 and adds a new subsequence, a 1 extends count0 sequences into count01, and a 2 extends count01 into count012. This approach is a classic dynamic programming pattern where each element updates states derived from previous states.
Approach 2: Iterative Counting with State Transition (O(n) time, O(1) space)
Process the array once and treat the problem as a finite state machine with three stages: building 0 subsequences, extending them to 01, and finally forming 012. Each number triggers a deterministic transition that either creates new subsequences or extends existing ones. Because every element contributes only constant-time updates to three counters, the algorithm runs in linear time. This version is often easier to reason about when thinking about subsequence transitions rather than explicit DP tables.
Approach 3: Iterative Approach with Optimization (O(n) time, O(1) space)
Instead of maintaining arrays or storing intermediate states for each index, keep only three variables representing the number of subsequences ending in each stage. Iterate through the array once and update these counters in place. Each update effectively doubles existing possibilities because every new element can either be included or skipped. The optimization eliminates auxiliary structures while preserving the same recurrence relation used in standard DP solutions.
Recommended for interviews: The state-based dynamic programming approach is what interviewers expect. It shows you can model subsequences as transitions between stages and reduce the DP table to constant space. Brute-force enumeration of subsequences demonstrates understanding but fails for large inputs, while the O(n) DP solution proves you can translate combinational counting into efficient state updates.
Approach 1: Dynamic Programming Approach
This approach utilizes a dynamic programming-like state tracking to count how many valid subsequences exist as you parse through the array. We maintain three variables representing different states: `count0` for subsequences ending with `0`, `count1` for subsequences ending with `1` after some `0`s, and `count2` for subsequences ending with `2` after some `0`s and `1`s. As we iterate through the list, we update these counts based on the current number. The total number of special subsequences is given by the value of `count2` at the end.
The function maintains three counters that represent how many subsequences can be formed that end with 0, 1, and 2 respectively. For each 0 encountered, we can either form a new subsequence or not, doubling the previous count and adding one. For a 1, we can add it to all subsequences ending with 0, while for a 2, we can add it to all subsequences ending with 1.
Complexity
Time Complexity: O(n) since we iterate through the number list once.
Space Complexity: O(1) as we use a constant amount of extra space.
Approach 2: Iterative Approach with Optimization
This approach is similar to the dynamic state tracking but focuses on maintaining distinct possible subsequences at each step. Instead of handling separate computations in terms of previous states, we optimize by updating subsequence counts directly using nested loops mimicry to express the combination of new possibilities.
The function effectively tags each number as either extending previous subsequences or initiating new ones, reflecting transitions between 0s, 1s, and 2s in special subsequences.
Code
JavaScript
Complexity
Time Complexity: O(n) because each element is processed once.
Space Complexity: O(1) as the space requirement does not grow with input size.
Approach 3: Iterative Counting with State Transition
This approach also makes use of iterative updating of subsequence counts, but emphasizes the concept of 'state transitions'. We define states as subsequences ending in a particular number. Each state expands when either a new element of the same number is included or transitioning from a previous state.
- State for subsequences ending in 0 updates by considering every new 0 encountered.
- State for subsequences ending in 1 updates by transitioning from valid subsequences of 0s.
- Similarly, state for subsequences ending in 2 transitions from those ending in 1s.
It uses the similar logic of strengthening subsequences by doubling the count when a new element of the same type is added, or by adding potential expands from previous state. The behavior is identical to previous approach.
Complexity
Time Complexity: O(n), Space Complexity: O(1).
Approach 4: 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
Code
Python
Java
C++
Go
TypeScript
Approach 5: 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n) since we iterate through the number list once. |
| Iterative Approach with Optimization | Time Complexity: O(n) because each element is processed once. |
| Iterative Counting with State Transition | Time Complexity: O(n), Space Complexity: O(1). |
| Dynamic Programming | — |
| Dynamic Programming (Space Optimization) | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with State Counts | O(n) | O(1) | Best general solution for interviews and large inputs |
| Iterative Counting with State Transition | O(n) | O(1) | When modeling subsequences as transitions between stages |
| Iterative Optimized Approach | O(n) | O(1) | When minimizing memory and keeping only running counters |
Video Solution
LeetCode 1955. Count Number of Special Subsequences • Happy Coding • 1,291 views views
Watch 7 more video solutions →Frequently Asked Questions
Is Count Number of Special Subsequences easy or hard?
Count Number of Special Subsequences Python/Java solution
How to solve Count Number of Special Subsequences in O(n)?
What is the best approach for Count Number of Special Subsequences?
Is Count Number of Special Subsequences asked at Google/Amazon/Meta?
What data structure is used in Count Number of Special Subsequences?
What is the time complexity of Count Number of Special Subsequences?
Ready to solve this problem?
Practice Count Number of Special Subsequences with our built-in code editor and test cases.
Practice on FleetCode