Is Number of Stable Subsequences easy or hard?

Number of Stable Subsequences is categorized as a Hard problem because it involves reasoning about subsequences and designing an efficient dynamic programming transition. Handling large input sizes often requires optimizing the DP with prefix structures or indexed trees.

Number of Stable Subsequences Python/Java solution

Python, Java, C++, and Go implementations typically use the same DP idea. Iterate through the array, maintain dp[i] for subsequences ending at index i, and accumulate results from earlier valid indices. The final answer is the sum of all dp values.

How to solve Number of Stable Subsequences in O(n)?

A pure O(n) solution generally isn't possible unless the stability condition restricts transitions to constant-time updates. Most implementations rely on dynamic programming where each element depends on earlier ones. Optimized versions can reach O(n log n) using prefix structures or indexed trees.

What is the best approach for Number of Stable Subsequences?

Dynamic programming on subsequences is the most practical approach. Define dp[i] as the number of stable subsequences ending at index i and extend it using earlier elements that satisfy the stability rule. This reduces the exponential subsequence search to O(n^2) time and O(n) space.

Is Number of Stable Subsequences asked at Google/Amazon/Meta?

Subsequence counting problems with dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving constraints between adjacent elements or value ranges are common because they test DP state design and transition reasoning.

What data structure is used in Number of Stable Subsequences?

The core solution uses arrays for dynamic programming states. Optimized implementations may add Fenwick trees or segment trees to aggregate counts across value ranges efficiently while processing the array.

What is the time complexity of Number of Stable Subsequences?

The standard dynamic programming solution runs in O(n^2) time because each element checks all previous elements to determine valid transitions. Space complexity is O(n) for storing the dp array. With value-based optimizations using Fenwick or segment trees, the transition step can drop to O(log n), giving O(n log n) time.

Description Hints 4 Video 18:38

3686. Number of Stable Subsequences

Hard58.9% acceptance1 company

You are given an integer array nums.

A subsequence is stable if it does not contain three consecutive elements with the same parity when the subsequence is read in order (i.e., consecutive inside the subsequence).

Return the number of stable subsequences.

Since the answer may be too large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [1,3,5]

Output: 6

Explanation:

Stable subsequences are [1], [3], [5], [1, 3], [1, 5], and [3, 5].
Subsequence [1, 3, 5] is not stable because it contains three consecutive odd numbers. Thus, the answer is 6.

Example 2:

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

Output: 14

Explanation:

The only subsequence that is not stable is [2, 4, 2], which contains three consecutive even numbers.
All other subsequences are stable. Thus, the answer is 14.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁵

Asked at 1 company

Google

Topics

Array Dynamic Programming

Hints open one at a time

Hint 1

Any subsequence of length 1 or 2 is always stable.

Hint 2

A subsequence becomes invalid only if you add a third consecutive element of the same parity.

Hint 3

Use DP tracking the last element’s parity and how many consecutive of that parity you have (1 or 2).

Hint 4

For each new number, either start a new subsequence, extend with same parity (if count < 2), or extend with different parity (reset count = 1).

LanguageLoading editor…

1class Solution:
2    def countStableSubsequences(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,3,5]

Input

[2,3,4,2]

Your code is saved on this device.