Scale Engineer

Count Number of Special Subsequences

Hard
#1782Time: O(N * 2^N). There are 2^N subsequences to generate. For each subsequence, the `isSpecial()` check can take up to O(N) time.Space: O(N), where N is the length of `nums`. This is due to the recursion depth and the space required to store the current subsequence being built.
Patterns
Dynamic Programming
Data structures
Array

Prompt

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 109 + 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.

 

Example 1:

Input: nums = [0,1,2,2]
Output: 3
Explanation: 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
Explanation: There are no special subsequences in [2,2,0,0].

Example 3:

Input: nums = [0,1,2,0,1,2]
Output: 7
Explanation: 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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves generating every possible subsequence of the input array nums. For each subsequence generated, a check is performed to determine if it qualifies as a "special" subsequence. A counter is used to tally the total number of such special subsequences found.

Algorithm

  • Define a recursive function, say findSubsequences(index, currentList), to generate all subsequences.
  • The index parameter tracks the current position in the nums array, and currentList stores the subsequence being built.
  • Base Case: When index reaches the end of nums, check if currentList is a special subsequence using a helper function isSpecial().
  • If isSpecial() returns true, increment a global counter (modulo 10^9 + 7).
  • Recursive Step: For each element at index, make two recursive calls:
    1. One without including nums[index] in currentList.
    2. One including nums[index] in currentList.
  • The isSpecial(list) helper function verifies if a given list follows the 0...1...2... pattern with at least one of each number.

Walkthrough

The core of this method is a backtracking algorithm. We can define a recursive function that explores two choices for each element in the input array: either include it in the current subsequence or not. This process branches out, eventually generating all 2^N possible subsequences, where N is the length of nums.

When the recursion reaches the end of the array, we have a complete subsequence. We then pass this subsequence to a validation function, isSpecial(). This function checks if the subsequence adheres to the required structure: a non-empty sequence of 0s, followed by a non-empty sequence of 1s, and finally a non-empty sequence of 2s. If the subsequence is valid, we increment our total count. Because two subsequences are different if their chosen indices are different, this method correctly counts all valid combinations. However, its exponential nature makes it impractical for the given constraints.

Complexity

Time

O(N * 2^N). There are 2^N subsequences to generate. For each subsequence, the `isSpecial()` check can take up to O(N) time.

Space

O(N), where N is the length of `nums`. This is due to the recursion depth and the space required to store the current subsequence being built.

Trade-offs

Pros

  • Conceptually simple and directly follows the problem's definition of a subsequence.

  • Easy to implement for someone familiar with recursion and backtracking.

Cons

  • Extremely inefficient due to its exponential time complexity.

  • Will result in a 'Time Limit Exceeded' error on any reasonably sized input.

Solutions

class Solution {public  int countSpecialSubsequences(int[] nums) {    final int mod = (int)1 e9 + 7;    int n = nums.length;    int[][] f = new int[n][3];    f[0][0] = nums[0] == 0 ? 1 : 0;    for (int i = 1; i < n; ++i) {      if (nums[i] == 0) {        f[i][0] = (2 * f[i - 1][0] % mod + 1) % mod;        f[i][1] = f[i - 1][1];        f[i][2] = f[i - 1][2];      } else if (nums[i] == 1) {        f[i][0] = f[i - 1][0];        f[i][1] = (f[i - 1][0] + 2 * f[i - 1][1] % mod) % 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) % mod;      }    }    return f[n - 1][2];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem