Count Number of Special Subsequences — Problem & Solution
Count Number of Special Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Count Number of Special Subsequences is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A sequence is special if it consists of a positive number of 0s, followed by a positive number of 1s, followed by a positive number of 2s. For example [0,1,2] and [0,0,1,1,1,2] are special, while [2,1,0], [1] and [0,1,2,0] are not.
Given an array nums containing only the values 0, 1 and 2, return the number of different subsequences of nums that are special, modulo 10^9 + 7. Two subsequences are different when the sets of indices they use are different.
Example 1
Input: nums = [0,0,1,2,2]
Output: 9
Explanation: Any non-empty choice of the two 0s (3 ways), the single 1, and any non-empty choice of the two 2s (3 ways).
Example 2
Input: nums = [2,1,0]
Output: 0
Example 3
Input: nums = [0,1,0,1,2]
Output: 5
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 2
Hints for Count Number of Special Subsequences
Hint 1
Scan left to right and count the subsequences built so far by how far along the pattern they are: only 0s, then 0s followed by 1s, then complete.
Hint 2
A new
0can be appended to every 'only 0s' subsequence or start a new one:zeros = 2 · zeros + 1.Hint 3
A new
1extends every '0s then 1s' subsequence or the first 1 after any 'only 0s' one:ones = 2 · ones + zeros. Likewisetwos = 2 · twos + ones. The answer istwos.
How to solve Count Number of Special Subsequences
Classify every subsequence chosen so far by its stage in the pattern. When a new element arrives, each existing subsequence of a compatible stage can either take it or not, which doubles that stage, and the previous stage feeds new members into it.
Approach
- Keep three counters:
a(non-empty, only 0s),b(0s then a non-empty run of 1s),c(complete special subsequences). - On
0:a = 2a + 1— each old one with or without this 0, plus the 0 alone. - On
1:b = 2b + a— each oldbwith or without this 1, plus everyaextended by its first 1. - On
2:c = 2c + b— likewise. - Reduce modulo 10^9 + 7 after each step and return
c.
Why it works
A subsequence that is special (or a valid prefix of the pattern) stays one when extended only by an element equal to its current stage value or the next one, and only in that order. For each counter, the subsequences counted after the step are exactly the old ones (not taking the element), the old ones of the same stage taking it, and the old ones of the previous stage taking it as their first element of the new value — three disjoint groups, which is the update.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The counts double at every matching element and overflow quickly — reduce modulo 10^9 + 7 at every step and use 64-bit arithmetic for
2x + y. - A
1can only extend subsequences that already contain a 0 — that is why it addsa, not 1. - Equal values at different positions make different subsequences; never deduplicate by value.
Reference solution
Python
from typing import List
def countSpecialSubsequences(nums: List[int]) -> int:
MOD = 10 ** 9 + 7
a = b = c = 0
for x in nums:
if x == 0:
a = (2 * a + 1) % MOD
elif x == 1:
b = (2 * b + a) % MOD
else:
c = (2 * c + b) % MOD
return cJava
public static int countSpecialSubsequences(int[] nums) {
final long MOD = 1000000007L;
long a = 0, b = 0, c = 0;
for (int x : nums) {
if (x == 0) a = (2 * a + 1) % MOD;
else if (x == 1) b = (2 * b + a) % MOD;
else c = (2 * c + b) % MOD;
}
return (int) c;
}C++
int countSpecialSubsequences(vector<int>& nums) {
const long long MOD = 1000000007LL;
long long a = 0, b = 0, c = 0;
for (int x : nums) {
if (x == 0) a = (2 * a + 1) % MOD;
else if (x == 1) b = (2 * b + a) % MOD;
else c = (2 * c + b) % MOD;
}
return (int)c;
}JavaScript
var countSpecialSubsequences = function(nums) {
var MOD = 1000000007, a = 0, b = 0, c = 0;
for (var i = 0; i < nums.length; i++) {
if (nums[i] === 0) a = (2 * a + 1) % MOD;
else if (nums[i] === 1) b = (2 * b + a) % MOD;
else c = (2 * c + b) % MOD;
}
return c;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming