#1955

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Number of Special Subsequences

Learn to count all valid special subsequences in an array using state transition dynamic programming efficiently and correctly.

array dynamic programming

Problem Statement

Given an array nums containing only integers 0, 1, and 2, find the number of special subsequences. A sequence is special if it contains one or more 0s, followed by one or more 1s, then one or more 2s, maintaining original order. Return the count modulo 10^9 + 7.

A subsequence is formed by deleting zero or more elements without changing the order of remaining elements. Two subsequences are different if their selected indices differ. The array length can be up to 10^5, so an efficient state transition dynamic programming approach is required.

Examples

Example 1

Input: nums = [0,1,2,2]

Output: 3

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

There are no special subsequences in [2,2,0,0].

Example 3

Input: nums = [0,1,2,0,1,2]

Output: 7

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 <= 105
0 <= nums[i] <= 2

Solution Approach

Use State Variables for Each Stage

Define three counters: count0, count1, count2, representing subsequences ending with 0, 1, and 2. Iterate through nums, updating count0 when a 0 appears, count1 when a 1 appears using previous count0, and count2 when a 2 appears using previous count1. This approach captures the state transitions of special subsequences.

Apply Modular Arithmetic

Since the number of subsequences can be very large, take each addition modulo 10^9 + 7. Every update to count0, count1, and count2 should use modular addition to prevent integer overflow and ensure correctness for large arrays.

Iterate Once Through Array

Process the array in a single pass, updating counts according to the current number. This linear iteration combined with state transitions ensures O(n) time complexity while maintaining the pattern of 0s then 1s then 2s subsequences.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) for a single pass through nums. Space complexity is O(1) since only three counters are maintained regardless of array size. Modular arithmetic does not affect asymptotic complexity.

What Interviewers Usually Probe

Looking for an O(n) solution using dynamic programming states.
Expect candidate to handle large array sizes efficiently with modulo arithmetic.
Check if candidate recognizes sequence constraints of 0s, 1s, then 2s.

Common Pitfalls or Variants

Common pitfalls

Updating counts in wrong order, corrupting state transitions.
Forgetting to apply modulo 10^9 + 7 leading to overflow.
Miscounting subsequences by treating repeated elements incorrectly.

Follow-up variants

Count special subsequences allowing zeros to repeat after 2s.
Count sequences with 0,1,2,3 using similar state transitions.
Find longest special subsequence instead of total count.

FAQ

What is the primary pattern used in Count Number of Special Subsequences?

The primary pattern is state transition dynamic programming, tracking counts of subsequences ending in 0, 1, and 2.

Can this problem be solved without dynamic programming?

A brute-force approach exists but is infeasible for large arrays due to exponential subsequence growth.

Why do we need modulo 10^9 + 7?

The number of subsequences can exceed integer limits, so modulo prevents overflow and ensures correct results.

How do repeated numbers affect the count?

Repeated numbers increase subsequence combinations; each appearance updates counts based on previous state counts.

What is the time complexity for this problem?

Time complexity is O(n) using a single pass with state transition counters, which is efficient for arrays up to 10^5 elements.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        f = [[0] * 3 for _ in range(n)]
        f[0][0] = nums[0] == 0
        for i in range(1, n):
            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]
            elif 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]

Solution 2: 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)$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        n = len(nums)
        f = [[0] * 3 for _ in range(n)]
        f[0][0] = nums[0] == 0
        for i in range(1, n):
            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]
            elif 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]

Continue Practicing

#1959 minimum total space wasted with k resizing operations #1947 maximum compatibility score sum #1937 maximum number of points with cost