Number of Stable Subsequences - Solution & Explanation

Problem Overview: You are given an array and must count how many subsequences satisfy a specific stability rule defined between consecutive elements. The challenge is that subsequences are not required to be contiguous, so the number of possibilities grows exponentially. A direct enumeration quickly becomes infeasible, which pushes the solution toward dynamic programming.

Approach 1: Brute Force Subsequence Enumeration (O(2^n) time, O(n) space)

The most direct strategy generates every possible subsequence using recursion or bitmask enumeration. For each candidate subsequence, verify whether it satisfies the stability condition defined by the problem. This approach uses a simple depth‑first search: at each index you either include the element or skip it, then validate the resulting subsequence. The algorithm is useful for understanding the problem constraints and testing small inputs, but the exponential 2^n search space becomes impractical once the array length grows beyond ~20.

Approach 2: Dynamic Programming on Subsequences (O(n^2) time, O(n) space)

The key observation is that every stable subsequence can be extended from a smaller stable subsequence that ends at an earlier index. Define dp[i] as the number of stable subsequences that end with element nums[i]. Iterate through the array, and for each index i, look at all previous indices j < i. If the pair (nums[j], nums[i]) satisfies the stability rule, then every subsequence counted in dp[j] can extend to i. Add dp[j] to dp[i]. Each element also forms a subsequence of length 1, so initialize dp[i] = 1. The final answer is the sum of all dp[i]. This approach leverages dynamic programming to reuse results and avoids recomputing subsequences repeatedly.

The iteration structure is straightforward: two nested loops over the array. The outer loop selects the ending element, while the inner loop checks all earlier candidates that could extend into a valid stable subsequence. The method works well for moderate constraints and keeps the implementation simple.

Approach 3: DP with Value-Based Optimization (O(n log n) time, O(n) space)

If the stability rule depends on element values (for example ranges or ordering), you can optimize the transition step using prefix sums or a Fenwick/segment tree after coordinate compression. Instead of scanning all previous indices, query a range of valid values that can precede nums[i]. This reduces the transition cost from O(n) to O(log n). The idea combines array traversal with indexed data structures that accumulate DP counts efficiently.

Recommended for interviews: Start by describing the brute force subsequence enumeration to show you understand the search space. Then move quickly to the dynamic programming formulation where dp[i] represents stable subsequences ending at index i. Interviewers typically expect this DP transition because it demonstrates the ability to transform an exponential subsequence problem into a polynomial-time solution using state reuse.