{x}
blog image

Count Number of Special Subsequences

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

Solution Explanation

This problem asks to count the number of special subsequences in an array nums containing only integers 0, 1, and 2. A subsequence is special if it contains a positive number of 0s, followed by a positive number of 1s, and then a positive number of 2s. The solution uses dynamic programming to efficiently count these subsequences.

Approach:

Both solutions leverage dynamic programming. The difference lies in the space optimization. Solution 1 uses a 2D array to store intermediate results, while Solution 2 optimizes it to a 1D array. Both solutions follow the same core logic:

  1. Initialization: The dynamic programming table (either 2D or 1D) is initialized. f[i][j] (in Solution 1) or f[j] (in Solution 2) represents the count of special subsequences ending with j (0, 1, or 2) considering the first i+1 elements of nums. Solution 1's f[0][0] (or Solution 2's f[0]) is initialized to 1 if nums[0] is 0, otherwise 0.

  2. Iteration: The code iterates through the nums array. For each number nums[i]:

    • If nums[i] is 0, we can either extend existing subsequences ending in 0 (doubling their count) or create new subsequences consisting only of the current 0 (adding 1).
    • If nums[i] is 1, we can only extend subsequences ending in 0, adding those counts to the count of subsequences ending in 1.
    • If nums[i] is 2, we can only extend subsequences ending in 1, adding those counts to the count of subsequences ending in 2.

  3. Modulo Operation: Throughout the calculation, the modulo operation (% mod) is applied to prevent integer overflow, where mod = 10^9 + 7.

  4. Result: After iterating through all numbers, f[n-1][2] (Solution 1) or f[2] (Solution 2) will contain the total count of special subsequences.

Time Complexity Analysis:

Both solutions have a time complexity of O(n), where n is the length of the nums array. This is because the code iterates through the array once.

Space Complexity Analysis:

  • Solution 1: The space complexity is O(n) due to the 2D DP table f.
  • Solution 2: The space complexity is O(1) because it uses only a 1D array f of constant size (3). Solution 2 is therefore more space-efficient.

Example Walkthrough (Solution 2):

Let's trace countSpecialSubsequences([0,1,2,2]) using Solution 2:

  • Initially, f = [0, 0, 0].
  • nums[0] = 0: f becomes [1, 0, 0].
  • nums[1] = 1: f becomes [1, 1, 0] (1 from f[0], 0 from f[1]).
  • nums[2] = 2: f becomes [1, 1, 1] (1 from f[1], 0 from f[2]).
  • nums[3] = 2: f becomes [1, 1, 3] (1 from f[1], 1 from f[2]).

The final result is f[2] = 3, which is the correct answer.

The provided code in various languages implements these solutions. Solution 2 is generally preferred because of its better space complexity. Both solutions are correct and achieve the desired result, however.