Count Number of Special Subsequences: Phase-Based DP

You are given an array nums consisting only of 0s, 1s, and 2s. A special subsequence is a subsequence that contains a positive number of 0s, followed by a positive number of 1s, followed by a positive number of 2s. Return the number of different special subsequences, modulo 10^9 + 7.

This is LeetCode 1955: Count Number of Special Subsequences. For example, given nums = [0, 1, 2, 2], the answer is 3. The three special subsequences are [0, 1, 2] (using the first 2), [0, 1, 2] (using the second 2), and [0, 1, 2, 2] (using both 2s).

Why this problem matters

Subsequence counting problems come up frequently in interviews, and this one adds a twist: the subsequence must follow a strict phase order. You cannot just count arbitrary subsequences. You need to track which "phase" of the pattern you are in. This turns the problem into a state machine DP, where each element either extends the current phase or transitions you to the next one.

The same phase-based thinking applies to problems where you must collect items in a specific order, or where valid sequences have a rigid structure. Once you see the three-counter pattern here, you will recognize it in other problems that require tracking progression through ordered stages.

The brute force approach

The most direct approach is to enumerate all subsequences and check which ones are special. For each element, you either include it or skip it, giving 2^n possible subsequences. For each one, you verify the phase ordering: all 0s come before all 1s, which come before all 2s, and each group is non-empty.

This works, but 2^n is far too slow for arrays up to length 100,000. You need a way to count valid subsequences without listing them all.

The key insight: three counters tracking three phases

Think of building a special subsequence as moving through three phases. In phase 0, you are collecting 0s. In phase 1, you are collecting 1s. In phase 2, you are collecting 2s. A subsequence is special only if it completes all three phases.

Track three counters: dp[0], dp[1], and dp[2]. Each one counts the number of valid subsequences that have completed up to that phase.

When you encounter a value v in the array, you update dp[v] with this formula:

• dp[v] = 2 * dp[v] + dp[v-1]

(For v == 0, use +1 instead of +dp[v-1], since starting a new "all 0s" subsequence does not require a prior phase.)

Where does the 2x come from? Every existing subsequence that already ends at phase v faces a choice: include this new element or exclude it. That doubles the count. On top of that, every subsequence ending at the previous phase (dp[v-1]) can now extend into phase v by including this element. That adds dp[v-1] new subsequences.

Walking through it step by step

Let's trace through nums = [0, 1, 2, 2] to see the counters evolve.

The answer is dp[2] = 3. There are three special subsequences in the array [0, 1, 2, 2].

The DP solution

def count_special_subsequences(nums):
    MOD = 10**9 + 7
    dp = [0, 0, 0]
    for x in nums:
        if x == 0:
            dp[0] = (2 * dp[0] + 1) % MOD
        elif x == 1:
            dp[1] = (2 * dp[1] + dp[0]) % MOD
        else:
            dp[2] = (2 * dp[2] + dp[1]) % MOD
    return dp[2]

One pass through the array, three variables, constant work per element. The modular arithmetic keeps numbers in range since counts can grow exponentially.

Why this approach is correct

Every special subsequence must contain at least one 0, at least one 1, and at least one 2, in that order. The three counters exactly partition all valid partial subsequences by how far they have progressed through the phases.

When you see a 0, you are only updating dp[0]. No subsequence in dp[1] or dp[2] is affected because you would never add a 0 after already collecting 1s or 2s. Similarly, seeing a 1 only updates dp[1], and seeing a 2 only updates dp[2]. The phases never interfere with each other.

The 2 * dp[v] factor is correct because each existing subsequence ending at phase v independently decides to include or exclude the new element. The + dp[v-1] factor is correct because each subsequence ending at the previous phase can transition into phase v by including this element. No subsequence is double-counted because these two groups are disjoint: one group already had elements from phase v, the other did not.

Complexity analysis

This is optimal. You must read every element at least once, and three variables is the minimum state needed to track three phases.

Building blocks

1. Phase-based DP / state machine DP

The core idea is modeling the problem as movement through ordered phases. Each element either stays in the current phase or advances to the next. This pattern shows up in problems like Best Time to Buy and Sell Stock III, where you track states like "before first buy," "holding first stock," "after first sell," and so on.

The general template: define one counter per state, iterate through the input, and update only the counter that matches the current element's state. Transitions flow in one direction.

2. Subsequence counting with include/exclude

When counting subsequences, each new element gives every relevant existing subsequence a binary choice: include or exclude. This doubles the count of existing subsequences at that level. Combined with a "carry" from the previous level, you get the 2 * dp[v] + dp[v-1] formula.

This same doubling pattern appears in Distinct Subsequences, where matching characters double the ways to form a target string. The mechanism is the same: for every existing partial match, the new character is either used or skipped.

Edge cases

• All same values: an array like [0, 0, 0] has no 1s or 2s, so dp[2] stays at 0. The answer is 0, since no special subsequence can be formed.
• Minimum valid input: the shortest valid array is [0, 1, 2], which gives exactly 1 special subsequence.
• Large repeated segments: arrays like [0, 0, ..., 1, 1, ..., 2, 2, ...] produce astronomically large counts. The modular arithmetic in the solution handles this correctly.
• Values out of order: if the array is [2, 1, 0], you can never form a valid special subsequence because the 0 comes after the 1 and 2. The answer is 0, and the DP handles this naturally since dp[1] never gets a nonzero dp[0] to carry from before a 1 is seen.

Common mistakes

• Forgetting the modular arithmetic. The counts grow exponentially with repeated values. Without % MOD, you will get integer overflow in languages like C++ or Java, and unnecessarily large numbers in Python.
• Updating the wrong counter. It is tempting to update all three counters for every element. But each element only affects one phase. A 0 never changes dp[1] or dp[2].
• Using dp[v-1] for v == 0. When you see a 0, the "carry" is +1, not +dp[-1]. There is no phase before phase 0. Each new 0 starts a brand-new single-element subsequence.
• Confusing subsequences with subarrays. Subsequences can skip elements. The elements do not need to be adjacent. This is what makes the problem hard and why brute force is exponential.

From understanding to recall

You now see why three counters are enough, how the 2x + carry formula works, and why each element only touches one counter. But can you reproduce this from scratch in a week? The formula is simple, but under interview pressure, it is easy to forget whether the carry comes from dp[v-1] or dp[v+1], or whether the base case for 0 is +1 or +dp[0].

Spaced repetition bridges that gap. You revisit this problem at increasing intervals, write the three-line loop from memory, and after a few reps, the phase-based DP pattern becomes automatic. The include/exclude doubling and the phase transition carry lock into long-term memory.

Phase-based DP is one of roughly 60 reusable building blocks in the CodeBricks system. You practice each block individually until writing the solution is second nature. Problems like this one, Best Time to Buy and Sell Stock III, and Distinct Subsequences all share the same state-machine skeleton. Drilling them as a group is the fastest path to owning this entire category.

Related posts

• Distinct Subsequences - Another subsequence counting DP where include/exclude logic drives the recurrence
• Decode Ways - DP with phase transitions and conditional branching at each step