Count Number of Special Subsequences - Video Solutions

Problem Overview: Given an array containing only 0, 1, and 2, count subsequences that follow the pattern: one or more 0s, followed by one or more 1s, followed by one or more 2s. The order must be preserved but elements do not need to be contiguous.

Approach 1: Dynamic Programming with State Counts (O(n) time, O(1) space)

Track three running counts while iterating through the array. count0 represents subsequences containing only 0s. count01 represents subsequences that started with 0s and now include 1s. count012 represents complete special subsequences that include 0, 1, and 2. When you encounter a value, update the corresponding state using transitions: a 0 doubles existing count0 and adds a new subsequence, a 1 extends count0 sequences into count01, and a 2 extends count01 into count012. This approach is a classic dynamic programming pattern where each element updates states derived from previous states.

Approach 2: Iterative Counting with State Transition (O(n) time, O(1) space)

Process the array once and treat the problem as a finite state machine with three stages: building 0 subsequences, extending them to 01, and finally forming 012. Each number triggers a deterministic transition that either creates new subsequences or extends existing ones. Because every element contributes only constant-time updates to three counters, the algorithm runs in linear time. This version is often easier to reason about when thinking about subsequence transitions rather than explicit DP tables.

Approach 3: Iterative Approach with Optimization (O(n) time, O(1) space)

Instead of maintaining arrays or storing intermediate states for each index, keep only three variables representing the number of subsequences ending in each stage. Iterate through the array once and update these counters in place. Each update effectively doubles existing possibilities because every new element can either be included or skipped. The optimization eliminates auxiliary structures while preserving the same recurrence relation used in standard DP solutions.

Recommended for interviews: The state-based dynamic programming approach is what interviewers expect. It shows you can model subsequences as transitions between stages and reduce the DP table to constant space. Brute-force enumeration of subsequences demonstrates understanding but fails for large inputs, while the O(n) DP solution proves you can translate combinational counting into efficient state updates.