We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Number of Special Subsequences

Number: 2086

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given an array nums consisting only of the integers 0, 1, and 2, count the number of distinct subsequences that are “special”. A special subsequence is one that can be divided into three contiguous parts: a positive number of 0s, followed by a positive number of 1s, and ending with a positive number of 2s. The answer can be huge so return it modulo 10^9 + 7.

Key Insights

  • Use dynamic programming to count ways to form each valid part of the subsequence.
  • Maintain three counters:
    • One for forming valid subsequences made solely of 0s.
    • A second for subsequences that have a valid sequence of 0s followed by 1s.
    • A third for complete special subsequences (0s followed by 1s and then 2s).
  • Process the array in one pass and update the counters based on the current number.
  • Ensure to take modulo 10^9 + 7 at each update to avoid overflow.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the array. Space Complexity: O(1), as only a fixed number of counters are used.

Solution

We use three counters: count0, count01, and count012. As we iterate through the nums array, perform the following updates based on the current element:

  • When encountering a 0:
    • Each existing sequence of 0s can either include or exclude the new 0, so update count0 = count0 * 2 + 1 (the +1 accounts for starting a new subsequence with the current 0).
  • When encountering a 1:
    • A 1 can either be appended to any existing valid 0s subsequence forming a 0-1 sequence, or extend an existing 0-1 sequence. Thus, update count01 = count01 * 2 + count0.
  • When encountering a 2:
    • Similarly, update count012 = count012 * 2 + count01, incorporating the new 2 into existing complete subsequences or forming new ones from sequences of 0s and 1s. These transitions ensure that all valid subsequences forming the pattern 0+1+2 are counted. The final answer is count012 modulo 10^9 + 7.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Define the function specialSubsequences that takes a list of integers nums.
def specialSubsequences(nums):
    mod = 10**9 + 7  # The modulo for large numbers
    count0 = 0      # Counter for valid sequences of 0s
    count01 = 0     # Counter for valid sequences of 0s followed by 1s
    count012 = 0    # Counter for complete valid sequences (0s, then 1s, then 2s)
    
    # Iterate over each number in the array
    for num in nums:
        if num == 0:
            # For a 0, either start a new subsequence or extend existing ones.
            count0 = (2 * count0 + 1) % mod
        elif num == 1:
            # For a 1, either append to existing sequences of 0s to start the 1 part or double existing 0-1 sequences.
            count01 = (2 * count01 + count0) % mod
        elif num == 2:
            # For a 2, either append to existing 0-1 sequences to complete the special subsequence or extend existing ones.
            count012 = (2 * count012 + count01) % mod
    return count012

# Example usage:
print(specialSubsequences([0,1,2,2]))  # Expected output: 3
← Back to All Questions