Count Number of Special Subsequences - Practice Coding Problems

Count Number of Special Subsequences - 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 10⁹ + 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.

Input & Output

Example 1 — Basic Special Sequence

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

› Output: 1

💡 Note: The only subsequence is [0,1,2] itself, which follows the pattern: one 0, then one 1, then one 2.

Example 2 — Multiple Valid Subsequences

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

› Output: 7

💡 Note: Valid subsequences: [0,1,2], [0,1,1,2], [0,0,1,2], [0,0,1,1,2], [0,1,2] (second 0 with first 1), [0,1,2] (first 0 with second 1), [0,1,2] (second 0 with second 1).

Example 3 — No Valid Subsequences

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

› Output: 0

💡 Note: No subsequence can follow the required pattern of 0s→1s→2s since elements are in reverse order.

Constraints

1 ≤ nums.length ≤ 10⁵
nums[i] is either 0, 1, or 2

Visualization

Tap to expand

Understanding the Visualization

Input

Array with values 0, 1, and 2

Process

Find subsequences with pattern: 0s→1s→2s

Output

Count of valid special subsequences

Key Takeaway

🎯 Key Insight: Use DP to track how many ways we can build subsequences at each stage (0s only, 0s+1s, complete 0s+1s+2s)

Asked in

A Amazon 15 M Microsoft 12 G Google 8

The key insight is to use dynamic programming to track three states: subsequences ending with 0s only, 0s+1s, and complete 0s+1s+2s sequences. Best approach is DP with O(n) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check which ones are special
Dynamic Programming - Count Valid States	O(n)	O(1)	Use DP to count subsequences ending in each state (0s, 1s, 2s)

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all 2^n possible subsequences
For each subsequence, check if it's special (0s→1s→2s pattern)
Count valid subsequences and return modulo 10^9+7

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n possible subsequences

Validate

Check each subsequence for 0→1→2 pattern

Count

Count valid special subsequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int isSpecial(int* seq, int len) {
    if (len == 0) return 0;
    
    int state = 0; // 0: expecting 0s, 1: expecting 1s, 2: expecting 2s
    
    for (int i = 0; i < len; i++) {
        int num = seq[i];
        if (state == 0 && num == 0) {
            continue;
        } else if (state == 0 && num == 1) {
            state = 1;
        } else if (state == 1 && num == 1) {
            continue;
        } else if (state == 1 && num == 2) {
            state = 2;
        } else if (state == 2 && num == 2) {
            continue;
        } else {
            return 0;
        }
    }
    
    return state == 2;
}

int solution(int* nums, int n) {
    int count = 0;
    int* subseq = (int*)malloc(n * sizeof(int));
    
    // Generate all subsequences using bit manipulation
    for (int mask = 1; mask < (1 << n); mask++) {
        int len = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subseq[len++] = nums[i];
            }
        }
        
        // Check if subsequence is special
        if (isSpecial(subseq, len)) {
            count = (count + 1) % MOD;
        }
    }
    
    free(subseq);
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            nums[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n)

Generate 2^n subsequences, each takes O(n) time to validate

⚠ Quadratic Growth

Space Complexity

O(n)

Space for current subsequence and validation

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler