Count Number of Special Subsequences

Hard
1517.

Count Number of Special Subsequences

Count Number of Special Subsequences is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

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^5
  • 0 <= nums[i] <= 2
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var countSpecialSubsequences = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 0 <= nums[i] <= 2

Hints for Count Number of Special Subsequences

  1. 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.

  2. Hint 2

    A new 0 can be appended to every 'only 0s' subsequence or start a new one: zeros = 2 · zeros + 1.

  3. Hint 3

    A new 1 extends every '0s then 1s' subsequence or the first 1 after any 'only 0s' one: ones = 2 · ones + zeros. Likewise twos = 2 · twos + ones. The answer is twos.

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

  1. Keep three counters: a (non-empty, only 0s), b (0s then a non-empty run of 1s), c (complete special subsequences).
  2. On 0: a = 2a + 1 — each old one with or without this 0, plus the 0 alone.
  3. On 1: b = 2b + a — each old b with or without this 1, plus every a extended by its first 1.
  4. On 2: c = 2c + b — likewise.
  5. 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 1 can only extend subsequences that already contain a 0 — that is why it adds a, 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 c

Java

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