Count Number of Special Subsequences
01 · Problem
Call a sequence special if it is made of one or more 0s, followed by one or more 1s, followed by one or more 2s (in that order, nothing else). For example [0,1,2] and [0,0,1,1,1,2] are special, while [2,1,0], [1] and [0,1,2,0] are not.
You are given an array nums whose values are only 0, 1 or 2. Return how many subsequences of nums are special. Because the count can be huge, return it modulo 10^9 + 7.
A subsequence keeps the original relative order but may skip elements. Two subsequences are counted separately if they use a different set of indices, even when their values look identical. If no special subsequence exists, return 0.
02 · Examples
nums = [0,1,2,2]
3
The special subsequences are [0,1,2] (using the first 2), [0,1,2] (using the second 2) and [0,1,2,2].
nums = [2,2,0,0]
0
Every 2 comes before every 0, so no subsequence can have 0s, then 1s, then 2s. There are also no 1s at all.
nums = [0,1,2,0,1,2]
7
Exactly 7 index sets form a special subsequence, for example indices (0,1,2), (3,4,5), (0,1,5) and (0,1,2,5).
03 · Constraints
- 011 <= nums.length <= 105
- 020 <= nums[i] <= 2
- 03Return the answer modulo 109 + 7
04 · Optimal complexity
- Time
- O(n)
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.