Find All Possible Stable Binary Arrays II - Solution & Explanation

Problem Overview: Count the number of binary arrays that use exactly zero zeros and one ones while ensuring no more than limit identical values appear consecutively. The result must include every valid arrangement that satisfies both the count constraint and the stability rule.

Approach 1: Hash Map Memoization (Top-Down DP) (Time: O(zero * one * limit), Space: O(zero * one * limit))

Model the problem as dynamic programming with memoization. Each state represents how many zeros and ones remain, what the last placed value was, and how long the current streak is. A recursive function explores placing either a 0 or 1 if doing so does not exceed the limit. Results for states like (z, o, last, streak) are cached in a hash map so repeated subproblems are computed once. This avoids exponential recursion and turns the search into a bounded DP over all valid states. The approach is straightforward to implement and clearly expresses the constraint logic, making it a good first solution when exploring dynamic programming problems with state transitions.

Approach 2: Sorting + Prefix Sum Optimized DP (Time: O((zero + one) log (zero + one) + zero * one), Space: O(zero * one))

A more optimized solution focuses on counting sequences without explicitly tracking every streak length. Instead of iterating over each possible extension one step at a time, prefix sums aggregate counts of valid transitions. You compute how many ways exist to end with a zero or one for each combination of used zeros and ones. Prefix ranges help subtract invalid configurations where the streak would exceed limit. Sorting can be used to normalize block expansions and process transitions in consistent order while prefix sums enable constant-time range queries. This reduces the number of repeated calculations and converts the naive streak iteration into efficient range updates, a common optimization technique in prefix sum based DP counting problems.

The DP table typically tracks two states: arrays ending in 0 and arrays ending in 1. For each cell, transitions add valid contributions from previous cells while subtracting sequences that would violate the consecutive limit. Prefix sums make these additions and removals constant-time instead of iterating over every possible streak length.

Recommended for interviews: Start with the memoized DP using a hash map to show you understand the state space and constraint handling. Interviewers usually expect the optimized DP with prefix sums afterward because it improves performance from streak-based iteration to aggregated transitions. Demonstrating both approaches shows strong command of DP state design and optimization techniques.