You are given 3 positive integers zero, one, and limit.
A binary array arr is called stable if:
arr is exactly zero.arr is exactly one.arr with a size greater than limit must contain both 0 and 1.Return the total number of stable binary arrays.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: zero = 1, one = 1, limit = 2
Output: 2
Explanation:
The two possible stable binary arrays are [1,0] and [0,1], as both arrays have a single 0 and a single 1, and no subarray has a length greater than 2.
Example 2:
Input: zero = 1, one = 2, limit = 1
Output: 1
Explanation:
The only possible stable binary array is [1,0,1].
Note that the binary arrays [1,1,0] and [0,1,1] have subarrays of length 2 with identical elements, hence, they are not stable.
Example 3:
Input: zero = 3, one = 3, limit = 2
Output: 14
Explanation:
All the possible stable binary arrays are [0,0,1,0,1,1], [0,0,1,1,0,1], [0,1,0,0,1,1], [0,1,0,1,0,1], [0,1,0,1,1,0], [0,1,1,0,0,1], [0,1,1,0,1,0], [1,0,0,1,0,1], [1,0,0,1,1,0], [1,0,1,0,0,1], [1,0,1,0,1,0], [1,0,1,1,0,0], [1,1,0,0,1,0], and [1,1,0,1,0,0].
Constraints:
1 <= zero, one, limit <= 200In #3129 Find All Possible Stable Binary Arrays I, you must count binary arrays that use a fixed number of 0s and 1s while keeping the array stable, meaning no value appears more than limit times consecutively. A natural way to approach this is through dynamic programming.
Define a DP state such as dp[i][j][k], representing the number of valid arrays formed using i zeros and j ones where the last placed value is k. When extending the array, ensure that adding another 0 or 1 does not exceed the consecutive limit. To efficiently aggregate transitions over valid ranges, prefix sums can be used to avoid repeatedly summing previous states.
This optimization significantly reduces repeated calculations compared with naive enumeration. The DP table is filled iteratively while respecting the constraint on consecutive elements. The resulting approach runs in roughly O(zero × one) time with similar space usage, making it efficient for typical constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Prefix Sum Optimization | O(zero × one) | O(zero × one) |
Sahil & Sarra
Use these hints if you're stuck. Try solving on your own first.
Let <code>dp[a][b][c = 0/1][d]</code> be the number of stable arrays with exactly <code>a</code> 0s, <code>b</code> 1s and consecutive <code>d</code> value of <code>c</code>’s at the end.
Try each case by appending a 0/1 at last to get the inductions.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Prefix sums allow you to quickly compute transitions over a range of previous DP states instead of iterating through each possibility. This optimization reduces repeated calculations when enforcing the consecutive limit constraint.
Yes, similar problems involving constrained binary sequences and dynamic programming appear in technical interviews. They test understanding of DP state design, transition optimization, and handling constraints like consecutive limits.
The optimal approach uses dynamic programming combined with prefix sum optimization. DP tracks how many zeros and ones have been used and the last placed value, while prefix sums help efficiently enforce the limit on consecutive elements.
A multidimensional dynamic programming array is typically used to track counts of valid states. Prefix sum arrays or cumulative sums are added to efficiently aggregate transitions between states.