1955. Count Number of Special Subsequences
Problem Description
This problem involves finding the number of different subsequences in a given array that are considered 'special'. A subsequence is considered special if it consists of a sequence containing a positive number of 0
s, then a positive number of 1
s, followed by a positive number of 2
s. For example, [0, 1, 2]
and [0, 0, 1, 1, 1, 2]
are special subsequences, while [2, 1, 0]
, [1]
, or [0, 1, 2, 0]
are not.
The input array contains only integers 0
, 1
, and 2
. The task is to return the number of such special subsequences in the array. However, since the number of special subsequences could be very large, the output should be given modulo 10^9 + 7
.
It's important to note that a subsequence can be formed by deleting some or no elements from the array without changing the order of the remaining elements. Two subsequences are considered different if they consist of different indices from the original array.
Intuition
The intuition behind the solution is based on dynamic programming. We need to count the number of valid subsequences that end with 0
, 1
, and 2
separately. Since the array contains only 0
s, 1
s, and 2
s, we can maintain a running count of the number of valid subsequences up to the current index of the array.
Here's the logic behind counting:
- When encountering a
0
, we can either start a new subsequence or attach the0
to all existing subsequences that currently end with0
. This means we double the count plus one for the new subsequence starting with just this0
. - When encountering a
1
, we can attach it either to all subsequences that end with0
(making them end with1
now) or to all subsequences that end with1
. These actions are independent: attaching to the sequences that end with0
does not affect the ones that end with1
. So we perform addition and then double the count of subsequences that end with1
. - When encountering a
2
, we use the same logic as with the1
s. A2
can be attached to any subsequence that currently ends with a1
(thus creating or extending a special sequence), or to subsequences that already end with2
.
By applying this logic iteratively over the array, we can accumulate the counts. Since we want subsequences, the order of elements is crucial, and we're only going forward in the array, never backward. This forward-only approach fits perfectly with the dynamic programming strategy, as we can base the new counts on the previously calculated ones, ensuring that we do not count any sequence more than once.
Finally, the total number of special subsequences is the number we have accumulated that end with 2
, because every special subsequence must end with a 2
.
Learn more about Dynamic Programming patterns.
Solution Approach
The reference solution provided is an implementation of the dynamic programming approach described above. It uses an array f
with three elements to keep track of the count of special subsequences that end with 0
, 1
, and 2
, respectively. Let's dive into how this is implemented in the solution:
- We initialize the array
f
with zeros. However, if the first element of the inputnums
is a0
, we need to setf[0]
to1
, since that represents a subsequence starting with0
. - We iterate through the input
nums
from the second element onwards, applying the logic based on the value present innums[i]
. - When we find a
0
innums
,f[0]
is updated to(2 * f[0] + 1) % mod
. This captures the doubling of existing sequences ending in0
and adds one for the new sequence that starts with this0
. The% mod
operation ensures we stay within the bounds of the defined modulo. - Upon encountering a
1
, we updatef[1]
to(f[0] + 2 * f[1]) % mod
. This takes into account all the subsequences that can be formed by appending the1
to existing subsequences ending with0
, as well as doubling the subsequences that already end with1
. - Likewise, when a
2
is found,f[2]
gets updated with(f[1] + 2 * f[2]) % mod
. This adds all sequences ending with1
to those ending with2
, and also doubles existing subsequences that end with2
. - The iteration continues for all elements of
nums
. - Eventually, we return the value in
f[2]
because it holds the count of all special subsequences which properly end with a2
.
By only using a fixed-size array, the solution has an O(n)
time complexity, where n
is the length of the input array nums
, and O(1)
space complexity, as the size of the f
array is constant and does not depend on the input size.
The code simply follows these steps, applying the update formulas for each element of nums
.
It's important to note that this solution strategy takes advantage of the property that the final special subsequence must end with a 2
to calculate the result. The modulo operation is used to avoid integer overflow due to the possible large number of special subsequences.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we have the following input array: nums = [0, 1, 0, 2, 1]
. We need to find the number of special subsequences using dynamic programming.
We initialize our array f
with zeros: f = [0, 0, 0]
. This array will hold counts of special subsequences that end with 0
, 1
, and 2
.
-
We come across the first element,
0
. According to our strategy, we updatef[0]
by doubling the count and adding 1 for a new subsequence starting with this0
. Therefore,f = [1, 0, 0]
. -
The next element is
1
. We updatef[1]
to account for all subsequences that can be formed by appending this1
to existing0
ending sequences and doubling the1
ending sequences. As we had1
subsequence ending with0
, we add it to0
(existing count of1
ending sequences) and double the0
. Now,f = [1, 1, 0]
. -
The third element is
0
again. We updatef[0]
to2 * f[0] + 1
, resulting inf[0] = 3
. So,f = [3, 1, 0]
. This accounts for the subsequence starting with the second0
and doubling the count of existing0
ending sequences. -
Now we encounter a
2
. We updatef[2]
by takingf[1]
followed by a2
and doubling existing2
ending sequences:f[2] = f[1] + 2 * f[2]
, which yields a1
. So,f = [3, 1, 1]
. -
The last element is
1
. We updatef[1]
withf[0]
(sequences that get1
appended) plus double the existing1
ending sequences. Sof[1] = 3 + 2 * 1 = 5
, andf
becomes[3, 5, 1]
.
After this iteration, f[2]
contains the total count of special subsequences ending with 2
, which is 1
. Therefore, for nums = [0, 1, 0, 2, 1]
, the number of special subsequences is 1
.
For the result, we use modular arithmetic with mod = 10^9 + 7
to avoid large numbers that can result from the calculations, ensuring numbers are within bounds of integer values typically used in programming problems.
Solution Implementation
1from typing import List
2
3class Solution:
4 def countSpecialSubsequences(self, nums: List[int]) -> int:
5 # Define a large number mod for taking modulus to prevent overflow
6 MOD = 10**9 + 7
7
8 # Initialize count arrays for subsequences ending with 0, 1, and 2
9 count_subsequences = [0] * 3
10
11 # Handle the case for the first element
12 # If it's 0, we have one subsequence starting with 0
13 count_subsequences[0] = int(nums[0] == 0)
14
15 # Iterate through the elements starting from the second one
16 for i in range(1, len(nums)):
17 num = nums[i]
18
19 if num == 0:
20 # For a 0, we can either append it to an existing subsequence of 0s
21 # or start a new subsequence with this 0. So we double the existing
22 # count and add 1 for the new subsequence.
23 count_subsequences[0] = (2 * count_subsequences[0] + 1) % MOD
24
25 elif num == 1:
26 # For a 1, it can be appended to all existing subsequences of 1s and 0s.
27 # For subsequences of 0s, we can create new subsequences of 1s (hence f[0]).
28 count_subsequences[1] = (count_subsequences[0] + 2 * count_subsequences[1]) % MOD
29
30 else: # num == 2
31 # For a 2, we can append it to all existing subsequences of 2s and 1s.
32 # Sequences of 1s become new subsequences of 2s when a 2 is appended.
33 count_subsequences[2] = (count_subsequences[1] + 2 * count_subsequences[2]) % MOD
34
35 # Return the count of subsequences that end with 2, as these are the complete sequences of 0->1->2
36 return count_subsequences[2]
37
1class Solution {
2
3 // Method to count special subsequences in an array
4 public int countSpecialSubsequences(int[] nums) {
5
6 // Initialize the modulo constant (as per modulo 10^9 + 7)
7 final int MODULO = 1000000007;
8
9 // Length of the input array
10 int n = nums.length;
11
12 // Array to store counts for each number 0, 1, and 2
13 int[] counts = new int[3];
14
15 // If the first element of nums is 0, then there is one such subsequence
16 counts[0] = nums[0] == 0 ? 1 : 0;
17
18 // Iterate over the array starting from the second element
19 for (int i = 1; i < n; ++i) {
20 if (nums[i] == 0) {
21 // If we find a 0, then we double the count of subsequences
22 // ending with 0, and add one for the subsequence consisting of just this 0
23 counts[0] = (2 * counts[0] % MODULO + 1) % MODULO;
24 } else if (nums[i] == 1) {
25 // If we find a 1, count of subsequences ending with 1 is
26 // increased by count of subsequences ending with 0 and twice those ending with 1
27 counts[1] = (counts[0] + 2 * counts[1] % MODULO) % MODULO;
28 } else { // nums[i] == 2
29 // If we find a 2, count of subsequences ending with 2 is
30 // increased by count of subsequences ending with 1 and twice those ending with 2
31 counts[2] = (counts[1] + 2 * counts[2] % MODULO) % MODULO;
32 }
33 }
34
35 // Return the count of special subsequences that end with 2
36 return counts[2];
37 }
38}
39
1class Solution {
2public:
3 int countSpecialSubsequences(vector<int>& nums) {
4 // Initialize the modulo constant for large number arithmetic
5 const int MOD = 1e9 + 7;
6
7 // Calculate the size of the input vector
8 int n = nums.size();
9
10 // Initialize a frequency array to count subsequences ending with 0, 1, 2 respectively
11 int frequency[3] = {0};
12
13 // If the first number is 0, then we have one subsequence starting with 0
14 frequency[0] = nums[0] == 0;
15
16 // Iterate over the rest of the numbers
17 for (int i = 1; i < n; ++i) {
18 if (nums[i] == 0) {
19 // For a new 0, double the existing subsequences and add 1 for the new subsequence starting with this 0
20 frequency[0] = (2 * frequency[0] % MOD + 1) % MOD;
21 } else if (nums[i] == 1) {
22 // For a new 1, we can append it to all the subsequences of 0's and also double the existing subsequences of 1's
23 frequency[1] = (frequency[0] + 2 * frequency[1] % MOD) % MOD;
24 } else if (nums[i] == 2) {
25 // For a new 2, we can append it to all the subsequences of 1's and also double the existing subsequences of 2's
26 frequency[2] = (frequency[1] + 2 * frequency[2] % MOD) % MOD;
27 }
28 }
29
30 // Return the count of subsequences ending with 2, which represents all valid special subsequences
31 return frequency[2];
32 }
33};
34
1function countSpecialSubsequences(nums: number[]): number {
2 const mod = 1e9 + 7; // Define the modulus to prevent integer overflow
3 const lengthOfNums = nums.length;
4 const counts = [0, 0, 0]; // [countOfZeros, countOfOnes, countOfTwos]
5
6 // Initialize the count of subsequences starting with 0, if first element is 0
7 counts[0] = nums[0] === 0 ? 1 : 0;
8
9 // Loop through the numbers in the array
10 for (let i = 1; i < lengthOfNums; ++i) {
11 if (nums[i] === 0) {
12 // If the current element is 0, it can either form a new subsequence
13 // or get attached to existing subsequences of zeros
14 counts[0] = (2 * counts[0] + 1) % mod;
15 } else if (nums[i] === 1) {
16 // If the current element is 1, it can either start a new subsequence after
17 // every subsequence of zeros or get attached to existing subsequences of ones
18 counts[1] = (counts[0] + 2 * counts[1]) % mod;
19 } else if (nums[i] === 2) {
20 // If the current element is 2, it can either start a new subsequence after
21 // every subsequence of ones or get attached to existing subsequences of twos
22 counts[2] = (counts[1] + 2 * counts[2]) % mod;
23 }
24 }
25
26 // Return the total count of special subsequences ending with 2
27 return counts[2];
28}
29
Time and Space Complexity
The time complexity of the given code is O(n)
, where n
is the length of the input list nums
. This is because there is a single loop that iterates over the list nums
once, and within that loop, it performs a constant amount of work for updating the list f
.
The space complexity of the given code is O(1)
since the space used does not depend on the size of the input list nums
. Only a fixed-size list f
of length 3 is used for the entire algorithm, regardless of the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
Is the following code DFS or BFS?
void search(Node root) { if (!root) return; visit(root); root.visited = true; for (Node node in root.adjacent) { if (!node.visited) { search(node); } } }
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!