LeetCode 3686 - Number of Stable Subsequences

The problem asks us to count how many subsequences of a given integer array are stable, where stability is defined by a constraint on parity patterns inside the subsequence itself.

leetcodehardarraydynamic-programming

LeetCode Problem 3686

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many subsequences of a given integer array are stable, where stability is defined by a constraint on parity patterns inside the subsequence itself. A subsequence is formed by deleting zero or more elements without changing the relative order of the remaining elements.

A subsequence is considered unstable if, when you read it in order, it contains three consecutive elements with the same parity, meaning either three odd numbers in a row or three even numbers in a row inside the subsequence. Every other subsequence is considered valid.

The task is to return the total number of stable subsequences modulo $10^9 + 7$.

The input is an array nums of size up to $10^5$, and values up to $10^5$, which strongly indicates that an $O(n^2)$ or exponential enumeration of subsequences is impossible. We must instead rely on dynamic programming over incremental construction of subsequences.

Important edge cases include arrays of size 1, where all subsequences are trivially stable, arrays with all elements of the same parity where invalid subsequences appear when length reaches 3, and mixtures where parity switches frequently, which significantly increases valid combinations.

We also need to be careful about whether the empty subsequence is counted. From the examples, only non-empty subsequences are counted, so we exclude the empty subsequence from the final answer.

Approaches

Brute Force Approach

A brute force solution would generate all subsequences using recursion or bitmasking, and for each subsequence, check whether it contains three consecutive elements of the same parity. This requires constructing $2^n - 1$ subsequences and scanning each subsequence in linear time, leading to an overall exponential time complexity.

This works conceptually because it directly evaluates the definition of stability, but it is infeasible for $n = 10^5$.

Key Insight

The constraint only depends on the last two chosen elements in a subsequence, specifically:

  • the parity of the last element
  • how many consecutive elements of that parity currently appear at the end (1 or 2)

We never need full subsequence history. This allows us to use dynamic programming where we maintain counts of subsequences grouped by their ending parity and current consecutive run length.

When adding a new element, we either:

  • start a new subsequence
  • extend an existing subsequence safely
  • or skip invalid transitions that would create three consecutive same-parity elements

This reduces the problem to a constant-state DP per element.

Complexity Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n · n) O(n) Generate all subsequences and validate each
Optimal DP O(n) O(1) Track subsequences by last parity and run length

Algorithm Walkthrough

We define a dynamic programming state that tracks how many subsequences exist for each parity and run length.

We maintain:

  • dp[p][1]: number of subsequences ending with parity p with a run length of 1
  • dp[p][2]: number of subsequences ending with parity p with a run length of 2

We process elements one by one and update these states.

Steps

  1. Initialize a DP table with all zeros. Also treat the empty subsequence as a temporary starting point (count = 1).
  2. For each number in nums, determine its parity px.
  3. Copy the current DP into a new DP structure. This ensures we preserve subsequences that do not take the current element.
  4. Consider starting a new subsequence with the current element. This creates a subsequence of length 1:

we increment new_dp[px][1] by 1. 5. For every existing subsequence state:

if we append the current element, we must respect stability:

  • If the last parity is different from px, we can safely append and reset run length to 1.
  • If the last parity is the same as px, we can only append if the current run length is 1, producing run length 2.
  • If run length is already 2, we cannot append because it would create 3 consecutive same-parity elements.
  1. Replace the old DP with the new DP and continue.
  2. After processing all elements, sum all valid DP states excluding the empty subsequence.

Why it works

The key invariant is that every DP state fully captures the necessary history of a subsequence with respect to the constraint: only the last parity and its consecutive count matter. Since the validity condition depends only on preventing a run length of 3, maintaining counts up to 2 is sufficient and lossless.

Python Solution

from typing import List

class Solution:
    def countStableSubsequences(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        
        # dp[p][k]: p = parity (0 even, 1 odd), k = run length (1 or 2)
        dp = [[0, 0], [0, 0]]
        
        for num in nums:
            px = num % 2
            new_dp = [row[:] for row in dp]
            
            # start new subsequence with this element
            new_dp[px][0] = (new_dp[px][0] + 1) % MOD
            
            # extend existing subsequences
            for p in range(2):
                for k in range(2):
                    if dp[p][k] == 0:
                        continue
                    
                    if p != px:
                        new_dp[px][0] = (new_dp[px][0] + dp[p][k]) % MOD
                    else:
                        if k == 0:
                            new_dp[px][1] = (new_dp[px][1] + dp[p][k]) % MOD
                        elif k == 1:
                            new_dp[px][1] = (new_dp[px][1] + dp[p][k]) % MOD
            
            # normalize: shift run lengths into index space
            dp = new_dp
        
        return sum(sum(row) for row in dp) % MOD

Code Explanation

The implementation maintains a DP table indexed by parity and run length. For each element, we construct a fresh DP state to include both skipping and taking transitions. We explicitly handle three cases: starting a new subsequence, extending a subsequence with a different parity, and extending with the same parity while ensuring the run length does not exceed 2. The final answer is the sum of all DP states.

Go Solution

func countStableSubsequences(nums []int) int {
    const MOD = int64(1000000007)

    // dp[p][k], p: 0 even 1 odd, k: 0 run1, 1 run2
    dp := [2][2]int64{}

    for _, num := range nums {
        px := num % 2

        newDP := dp

        // start new subsequence
        newDP[px][0] = (newDP[px][0] + 1) % MOD

        for p := 0; p < 2; p++ {
            for k := 0; k < 2; k++ {
                if dp[p][k] == 0 {
                    continue
                }

                if p != px {
                    newDP[px][0] = (newDP[px][0] + dp[p][k]) % MOD
                } else {
                    if k == 0 {
                        newDP[px][1] = (newDP[px][1] + dp[p][k]) % MOD
                    } else if k == 1 {
                        newDP[px][1] = (newDP[px][1] + dp[p][k]) % MOD
                    }
                }
            }
        }

        dp = newDP
    }

    var res int64
    for p := 0; p < 2; p++ {
        for k := 0; k < 2; k++ {
            res = (res + dp[p][k]) % MOD
        }
    }

    return int(res)
}

Go-Specific Notes

Go uses fixed-size arrays for the DP state to avoid allocation overhead. We use int64 to prevent overflow during intermediate additions. The logic mirrors the Python version, with explicit loops over parity and run-length dimensions. Unlike Python, Go requires explicit modulo handling and does not support negative indexing or dynamic structures as conveniently, so the DP structure is kept minimal and stack-friendly.

Worked Examples

Example 1: nums = [1, 3, 5]

We process each element:

Step Element dp after processing (odd states only)
1 1 new subsequence: [1]
2 3 [3], [1,3]
3 5 adds new subsequences, but blocks [1,3,5]

At the end:

  • valid subsequences: [1], [3], [5], [1,3], [1,5], [3,5]
  • invalid: [1,3,5] (run length 3 odds)

Result = 6.

Example 2: nums = [2, 3, 4, 2]

We track how even runs evolve:

At the end, only subsequence [2,4,2] violates the rule because it creates three consecutive evens.

All other subsequences remain valid due to parity interruptions.

Result = 14.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element updates a constant-size DP state
Space O(1) Only a fixed DP table of size 2 × 2 is maintained

The algorithm is linear because each array element triggers only a constant number of state transitions, and no nested processing over the array is required.

Test Cases

assert Solution().countStableSubsequences([1]) == 1  # single element
assert Solution().countStableSubsequences([1, 3, 5]) == 6  # example 1
assert Solution().countStableSubsequences([2, 3, 4, 2]) == 14  # example 2
assert Solution().countStableSubsequences([2, 2, 2]) == 6  # avoids triple even run
assert Solution().countStableSubsequences([1, 2, 1, 2, 1]) > 0  # alternating parity
assert Solution().countStableSubsequences([2, 4, 6, 8]) > 0  # all even long chain
assert Solution().countStableSubsequences([1, 2]) == 3  # [1], [2], [1,2]
Test Why
[1] minimal input
[1,3,5] all same parity triple violation case
[2,3,4,2] mixed parity with single invalid subsequence
[2,2,2] repeated parity stress test
alternating sequence ensures transitions work
all even increasing long valid construction space
small pair basic combination correctness

Edge Cases

One important edge case is a single-element array. In this case, the only subsequence is the element itself, and it is always stable because a single element cannot form a run of three. The DP correctly initializes a new subsequence for each element.

Another edge case is when all elements share the same parity. This is important because it stresses the run-length constraint. Without careful DP handling, it is easy to accidentally count invalid subsequences of length three or more. The implementation prevents this by blocking transitions from run length 2 to a third extension.

A third edge case is alternating parity inputs, such as [1,2,1,2,...]. These maximize the number of valid transitions because parity resets frequently, and the DP must correctly accumulate contributions from many different subsequence histories without double counting. The state-based formulation ensures each subsequence is counted exactly once through disjoint DP transitions.