Count Number of Special Subsequences solution and explanation
7 more videos on this problem
LeetCode 1955. Count Number of Special SubsequencesHappy Coding · 14:12 · 1K views
Leetcode 1955 Count Number of Special SubsequencesSandip Jana · 12:08 · 1K views
Count Number of Special Subsequences Leetcode Hard 1955 Leetcode Weekly Contest 252CodeinDepth · 18:46 · 589 views
1955. Count Number of Special Subsequences (Leetcode Hard)Programming Live with Larry · 20:38 · 514 views
LeetCode 1955. Count Number Of Special Subsequences (Hard) | Dynamic Programming | C++Ascorbichelix · 14:13 · 328 views
【每日一题】1955. Count Number of Special Subsequences, 8/3/2021Huifeng Guan · 24:34 · 305 views
1955. (Hard) Count Number of Special Subsequences - Daily Leetcode (Day 74)yeetcode · 5:36 · 85 views
LeetCode 1955: Count Number of Special SubsequencesAlitaCode · 29:03
The 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 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.
def countSpecialSubsequences(nums):
MOD = 10**9 + 7
count0 = count1 = count2 = 0
for n in nums:
if n == 0:
count0 = (count0 * 2 + 1) % MOD
elif n == 1:
count1 = (count1 * 2 + count0) % MOD
elif n == 2:
count2 = (count2 * 2 + count1) % MOD
return count2
# Example usage
nums = [0,1,2,0,1,2]
print(countSpecialSubsequences(nums)) # Output: 7The 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.
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.
function countSpecialSubsequences(nums) {
const MOD = 1000000007;
let count0 = 0, count1 = 0, count2 = 0;
for (let num of nums) {
if (num === 0) {
count0 = (count0 * 2 + 1) % MOD;
} else if (num === 1) {
count1 = (count1 * 2 + count0) % MOD;
} else if (num === 2) {
count2 = (count2 * 2 + count1) % MOD;
}
}
return count2;
}
// Example usage
let nums = [0, 1, 2, 0, 1, 2];
console.log(countSpecialSubsequences(nums)); // Output: 7The function effectively tags each number as either extending previous subsequences or initiating new ones, reflecting transitions between 0s, 1s, and 2s in special subsequences.
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: Dynamic Programming Approach
The idea is to use dynamic programming to keep track of the number of special subsequences ending in 0, 1, and 2. Let’s maintain three counters: `count0`, `count1`, and `count2`. As we traverse the numbers, we update these counts based on the conditions:
- When encountering a 0, it can either start a new subsequence or continue another subsequence that was ending with 0. Hence, `count0` is updated to be `count0*2 + 1`.
- When encountering a 1, it can only continue an existing `0` subsequence. Hence, `count1` becomes `count1*2 + count0`.
- When encountering a 2, it can only continue an existing `1` subsequence. Therefore, `count2` is updated as `count2*2 + count1`.
We return `count2` as it represents the number of special subsequences following the `0, 1, 2` pattern.
class Solution {
private static final int MOD = 1000000007;
public int countSpecialSubsequences(int[] nums) {
long count0 = 0, count1 = 0, count2 = 0;
for (int num : nums) {
if (num == 0) {
count0 = (2 * count0 + 1) % MOD;
} else if (num == 1) {
count1 = (2 * count1 + count0) % MOD;
} else if (num == 2) {
count2 = (2 * count2 + count1) % MOD;
}
}
return (int) count2;
}
}#include <vector>
using namespace std;
class Solution {
public:
int countSpecialSubsequences(vector<int>& nums) {
long count0 = 0, count1 = 0, count2 = 0;
int MOD = 1e9 + 7;
for (int num : nums) {
if (num == 0) {
count0 = (2 * count0 + 1) % MOD;
} else if (num == 1) {
count1 = (2 * count1 + count0) % MOD;
} else if (num == 2) {
count2 = (2 * count2 + count1) % MOD;
}
}
return count2;
}
};const MOD = 1e9 + 7;
function countSpecialSubsequences(nums) {
let count0 = 0, count1 = 0, count2 = 0;
for (let num of nums) {
if (num === 0) {
count0 = (2 * count0 + 1) % MOD;
} else if (num === 1) {
count1 = (2 * count1 + count0) % MOD;
} else if (num === 2) {
count2 = (2 * count2 + count1) % MOD;
}
}
return count2;
}#define MOD 1000000007
int countSpecialSubsequences(int* nums, int numsSize) {
long count0 = 0, count1 = 0, count2 = 0;
for (int i = 0; i < numsSize; ++i) {
int num = nums[i];
if (num == 0) {
count0 = (2 * count0 + 1) % MOD;
} else if (num == 1) {
count1 = (2 * count1 + count0) % MOD;
} else if (num == 2) {
count2 = (2 * count2 + count1) % MOD;
}
}
return (int)count2;
}public class Solution {
private const int MOD = 1000000007;
public int CountSpecialSubsequences(int[] nums) {
long count0 = 0, count1 = 0, count2 = 0;
foreach (int num in nums) {
if (num == 0) {
count0 = (2 * count0 + 1) % MOD;
} else if (num == 1) {
count1 = (2 * count1 + count0) % MOD;
} else if (num == 2) {
count2 = (2 * count2 + count1) % MOD;
}
}
return (int)count2;
}
}This Java solution defines constants for modular arithmetic and updates counting variables within a loop as it iterates over the input array. The strategy follows the same logical pattern, modifying each counter according to potential subsequence continuations.
Time Complexity: O(n), with n being the size of the array. Space Complexity: O(1).
Approach 4: 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.
MOD = 10**9 + 7
def countSpecialSubsequences(nums):
count0, count1, count2 = 0, 0, 0
for num in nums:
if num == 0:
count0 = (count0 * 2 + 1) % MOD
elif num == 1:
count1 = (count1 * 2 + count0) % MOD
elif num == 2:
count2 = (count2 * 2 + count1) % MOD
return count2class Solution {
public int countSpecialSubsequences(int[] nums) {
long count0 = 0, count1 = 0, count2 = 0;
int MOD = 1000000007;
for (int num : nums) {
if (num == 0) {
count0 = (count0 * 2 + 1) % MOD;
} else if (num == 1) {
count1 = (count1 * 2 + count0) % MOD;
} else if (num == 2) {
count2 = (count2 * 2 + count1) % MOD;
}
}
return (int) count2;
}
}#include <vector>
class Solution {
public:
int countSpecialSubsequences(std::vector<int>& nums) {
int count0 = 0, count1 = 0, count2 = 0;
int MOD = 1000000007;
for (auto &num : nums) {
if (num == 0) {
count0 = (count0 * 2 + 1) % MOD;
} else if (num == 1) {
count1 = (count1 * 2 + count0) % MOD;
} else if (num == 2) {
count2 = (count2 * 2 + count1) % MOD;
}
}
return count2;
}
};const MOD = 1e9 + 7;
function countSpecialSubsequences(nums) {
let count0 = 0, count1 = 0, count2 = 0;
for (let num of nums) {
if (num === 0) {
count0 = (count0 * 2 + 1) % MOD;
} else if (num === 1) {
count1 = (count1 * 2 + count0) % MOD;
} else if (num === 2) {
count2 = (count2 * 2 + count1) % MOD;
}
}
return count2;
}#define MOD 1000000007
int countSpecialSubsequences(int* nums, int numsSize) {
long count0 = 0, count1 = 0, count2 = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] == 0) {
count0 = (count0 * 2 + 1) % MOD;
} else if (nums[i] == 1) {
count1 = (count1 * 2 + count0) % MOD;
} else if (nums[i] == 2) {
count2 = (count2 * 2 + count1) % MOD;
}
}
return (int)count2;
}public class Solution {
private const int MOD = 1000000007;
public int CountSpecialSubsequences(int[] nums) {
long count0 = 0, count1 = 0, count2 = 0;
foreach (int num in nums) {
if (num == 0) {
count0 = (count0 * 2 + 1) % MOD;
} else if (num == 1) {
count1 = (count1 * 2 + count0) % MOD;
} else if (num == 2) {
count2 = (count2 * 2 + count1) % MOD;
}
}
return (int) count2;
}
}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.
Time Complexity: O(n), Space Complexity: O(1).
Approach 5: 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
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];
}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]
}Approach 6: 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.
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];
}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]
}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. |
| Dynamic Programming Approach | Time Complexity: O(n), with n being the size of the array. Space Complexity: O(1). |
| Iterative Counting with State Transition | Time Complexity: O(n), Space Complexity: O(1). |
| Dynamic Programming | – |
| Dynamic Programming (Space Optimization) | – |
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 |
Frequently asked questions
Is Count Number of Special Subsequences easy or hard?
Count Number of Special Subsequences is rated Hard because it requires recognizing a subsequence pattern and modeling it with dynamic programming state transitions. Once the three-state DP pattern is understood, the implementation becomes straightforward.
Count Number of Special Subsequences Python/Java solution
Both Python and Java implementations follow the same DP idea. Maintain three variables for counts of 0, 01, and 012 subsequences and update them during a single pass through the array. The logic is identical across languages with only syntax differences.
How to solve Count Number of Special Subsequences in O(n)?
Maintain three counters: count0, count01, and count012. For each element, update the counters based on whether the value is 0, 1, or 2. A 0 doubles existing 0-only subsequences, a 1 extends 0 subsequences into 01 subsequences, and a 2 extends 01 subsequences into complete 012 subsequences.
What is the best approach for Count Number of Special Subsequences?
The optimal approach uses dynamic programming with three state counters: sequences of 0s, sequences of 0s followed by 1s, and sequences of 0s→1s→2s. As you iterate through the array, each number updates one of these states. This solution runs in O(n) time and O(1) space and is the standard interview approach.
Is Count Number of Special Subsequences asked at Google/Amazon/Meta?
Variants of subsequence counting and dynamic programming state transition problems appear frequently in interviews at companies like Google, Amazon, and Meta. Problems involving pattern-based subsequences and combinational counting are common in senior-level coding rounds.
What data structure is used in Count Number of Special Subsequences?
The solution primarily uses dynamic programming with simple integer counters rather than complex data structures. The input is processed as an array while maintaining three state variables that represent different subsequence stages.
What is the time complexity of Count Number of Special Subsequences?
The optimal solution runs in O(n) time because the array is scanned once and each element performs constant-time state updates. Space complexity is O(1) since only three counters are stored instead of a full DP table.