Skip to content

1955. Count Number of Special Subsequences 👍

Approach 1: Top-down

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int countSpecialSubsequences(vector<int>& nums) {
    vector<vector<int>> mem(nums.size(), vector<int>(4, -1));
    return countSpecialSubsequences(nums, 0, -1, mem);
  }

 private:
  static constexpr int kMod = 1'000'000'007;

  // Returns the number of increasing subsequences of the first i numbers, where
  // the previous number is `prev`.
  int countSpecialSubsequences(const vector<int>& nums, int i, int prev,
                               vector<vector<int>>& mem) {
    if (i == nums.size())
      return prev == 2;
    const int j = prev + 1;  // Map -1/0/1/2 to 0/1/2/3 respectively.
    if (mem[i][j] != -1)
      return mem[i][j];

    long res = 0;

    // Don't include `nums[i]`.
    res += countSpecialSubsequences(nums, i + 1, prev, mem);

    // Include `nums[i]`.
    if (nums[i] == prev)
      res += countSpecialSubsequences(nums, i + 1, prev, mem);
    if (prev == -1 && nums[i] == 0)
      res += countSpecialSubsequences(nums, i + 1, 0, mem);
    if (prev == 0 && nums[i] == 1)
      res += countSpecialSubsequences(nums, i + 1, 1, mem);
    if (prev == 1 && nums[i] == 2)
      res += countSpecialSubsequences(nums, i + 1, 2, mem);

    res %= kMod;
    return mem[i][j] = res;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int countSpecialSubsequences(int[] nums) {
    Integer[][] mem = new Integer[nums.length][4];
    return countSpecialSubsequences(nums, 0, -1, mem);
  }

  private static final int kMod = 1_000_000_007;

  // Returns the number of increasing subsequences of the first i numbers, where
  // the previous number is `prev`.
  int countSpecialSubsequences(int[] nums, int i, int prev, Integer[][] mem) {
    if (i == nums.length)
      return prev == 2 ? 1 : 0;
    final int j = prev + 1; // Map -1/0/1/2 to 0/1/2/3 respectively.
    if (mem[i][j] != null)
      return mem[i][j];

    long res = 0;

    // Don't include `nums[i]`.
    res += countSpecialSubsequences(nums, i + 1, prev, mem);

    // Include `nums[i]`.
    if (nums[i] == prev)
      res += countSpecialSubsequences(nums, i + 1, prev, mem);
    if (prev == -1 && nums[i] == 0)
      res += countSpecialSubsequences(nums, i + 1, 0, mem);
    if (prev == 0 && nums[i] == 1)
      res += countSpecialSubsequences(nums, i + 1, 1, mem);
    if (prev == 1 && nums[i] == 2)
      res += countSpecialSubsequences(nums, i + 1, 2, mem);

    res %= kMod;
    return mem[i][j] = (int) res;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
  def countSpecialSubsequences(self, nums: List[int]) -> int:
    kMod = 1_000_000_007

    @functools.lru_cache(None)
    def dp(i: int, prev: int) -> int:
      """
      Returns the number of increasing subsequences of the first i numbers,
      where the the previous number is j - 1.
      """
      if i == len(nums):
        return prev == 2

      res = 0

      # Don't include `nums[i]`.
      res += dp(i + 1, prev)

      # Include `nums[i]`.
      if nums[i] == prev:
        res += dp(i + 1, prev)
      if prev == -1 and nums[i] == 0:
        res += dp(i + 1, 0)
      if prev == 0 and nums[i] == 1:
        res += dp(i + 1, 1)
      if prev == 1 and nums[i] == 2:
        res += dp(i + 1, 2)

      res %= kMod
      return res

    return dp(0, -1)

Approach 2: Bottom-up 1D DP

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int countSpecialSubsequences(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    // dp[i][j] := the number of increasing subsequences of the first i numbers
    // that end in j
    vector<vector<long>> dp(n, vector<long>(3));

    if (nums[0] == 0)
      dp[0][0] = 1;

    for (int i = 1; i < n; ++i) {
      for (int ending = 0; ending < 3; ++ending)
        dp[i][ending] = dp[i - 1][ending];

      if (nums[i] == 0)
        // 1. The number of the previous subsequences that end in 0.
        // 2. Append a 0 to the previous subsequences that end in 0.
        // 3. Start a new subsequence from this 0.
        dp[i][0] = dp[i - 1][0] * 2 + 1;
      else if (nums[i] == 1)
        // 1. The number of the previous subsequences that end in 1.
        // 2. Append a 1 to the previous subsequences that end in 1.
        // 3. Append a 1 to the previous subsequences that end in 0.
        dp[i][1] = dp[i - 1][1] * 2 + dp[i - 1][0];
      else  // nums[i] == 2
        // 1. The number of the previous subsequences that end in 2.
        // 2. Append a 2 to the previous subsequences that end in 2.
        // 3. Append a 2 to the previous subsequences that end in 1.
        dp[i][2] = dp[i - 1][2] * 2 + dp[i - 1][1];

      for (int ending = 0; ending < 3; ++ending)
        dp[i][ending] %= kMod;
    }

    return dp.back()[2];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
  public int countSpecialSubsequences(int[] nums) {
    final int kMod = 1_000_000_007;
    final int n = nums.length;
    // dp[i][j] := the number of increasing subsequences of the first i numbers
    // that end in j
    long[][] dp = new long[n][3];

    if (nums[0] == 0)
      dp[0][0] = 1;

    for (int i = 1; i < n; ++i) {
      for (int ending = 0; ending < 3; ++ending)
        dp[i][ending] = dp[i - 1][ending];

      if (nums[i] == 0)
        // 1. The number of the previous subsequences that end in 0.
        // 2. Append a 0 to the previous subsequences that end in 0.
        // 3. Start a new subsequence from this 0.
        dp[i][0] = dp[i - 1][0] * 2 + 1;
      else if (nums[i] == 1)
        // 1. The number of the previous subsequences that end in 1.
        // 2. Append a 1 to the previous subsequences that end in 1.
        // 3. Append a 1 to the previous subsequences that end in 0.
        dp[i][1] = dp[i - 1][1] * 2 + dp[i - 1][0];
      else // nums[i] == 2
        // 1. The number of the previous subsequences that end in 2.
        // 2. Append a 2 to the previous subsequences that end in 2.
        // 3. Append a 2 to the previous subsequences that end in 1.
        dp[i][2] = dp[i - 1][2] * 2 + dp[i - 1][1];

      for (int ending = 0; ending < 3; ++ending)
        dp[i][ending] %= kMod;
    }

    return (int) dp[n - 1][2];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
  def countSpecialSubsequences(self, nums: List[int]) -> int:
    kMod = 1_000_000_007
    n = len(nums)
    # dp[i][j] := the number of increasing subsequences of the first i numbers
    # that end in j
    dp = [[0] * 3 for _ in range(n)]

    if nums[0] == 0:
      dp[0][0] = 1

    for i in range(1, n):
      for ending in range(3):
        dp[i][ending] = dp[i - 1][ending]

      if nums[i] == 0:
        # 1. The number of the previous subsequences that end in 0.
        # 2. Append a 0 to the previous subsequences that end in 0.
        # 3. Start a new subsequence from this 0.
        dp[i][0] = dp[i - 1][0] * 2 + 1
      elif nums[i] == 1:
        # 1. The number of the previous subsequences that end in 1.
        # 2. Append a 1 to the previous subsequences that end in 1.
        # 3. Append a 1 to the previous subsequences that end in 0.
        dp[i][1] = dp[i - 1][1] * 2 + dp[i - 1][0]
      else:  # nums[i] == 2
        # 1. The number of the previous subsequences that end in 2.
        # 2. Append a 2 to the previous subsequences that end in 2.
        # 3. Append a 2 to the previous subsequences that end in 1.
        dp[i][2] = dp[i - 1][2] * 2 + dp[i - 1][1]

      for ending in range(3):
        dp[i][ending] %= kMod

    return dp[-1][2]

Approach 3: Bottom-up $O(1)$ DP

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int countSpecialSubsequences(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    // dp[j] := the number of increasing subsequences of the numbers so far that
    // end in j
    vector<long> dp(3);

    if (nums[0] == 0)
      dp[0] = 1;

    for (int i = 1; i < n; ++i) {
      if (nums[i] == 0)
        dp[0] = dp[0] * 2 + 1;
      else if (nums[i] == 1)
        dp[1] = dp[1] * 2 + dp[0];
      else  // nums[i] == 2
        dp[2] = dp[2] * 2 + dp[1];

      for (int ending = 0; ending < 3; ++ending)
        dp[ending] %= kMod;
    }

    return dp[2];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
  public int countSpecialSubsequences(int[] nums) {
    final int kMod = 1_000_000_007;
    final int n = nums.length;
    // dp[j] := the number of increasing subsequences of the numbers so far that
    // end in j
    long[] dp = new long[3];

    if (nums[0] == 0)
      dp[0] = 1;

    for (int i = 1; i < n; ++i) {
      if (nums[i] == 0)
        dp[0] = dp[0] * 2 + 1;
      else if (nums[i] == 1)
        dp[1] = dp[1] * 2 + dp[0];
      else // nums[i] == 2
        dp[2] = dp[2] * 2 + dp[1];

      for (int ending = 0; ending < 3; ++ending)
        dp[ending] %= kMod;
    }

    return (int) dp[2];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
  def countSpecialSubsequences(self, nums: List[int]) -> int:
    kMod = 1_000_000_007
    n = len(nums)
    # dp[j] := the number of increasing subsequences of the numbers so far that
    # end in j
    dp = [0] * 3

    if nums[0] == 0:
      dp[0] = 1

    for i in range(1, n):
      if nums[i] == 0:
        dp[0] = dp[0] * 2 + 1
      elif nums[i] == 1:
        dp[1] = dp[1] * 2 + dp[0]
      else:  # nums[i] == 2
        dp[2] = dp[2] * 2 + dp[1]

      for ending in range(3):
        dp[ending] %= kMod

    return dp[2]