1955. Count Number of Special Subsequences LeetCode Solution
In this guide, you will get 1955. Count Number of Special Subsequences LeetCode Solution with the best time and space complexity. The solution to Count Number of Special Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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].
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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1955. Count Number of Special Subsequences LeetCode Solution in C++
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;
}
}; /* code provided by PROGIEZ */
1955. Count Number of Special Subsequences LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
1955. Count Number of Special Subsequences LeetCode Solution in Python
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) # code by PROGIEZ
