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].
Example 2:
Input: zero = 1, one = 2, limit = 1
Output: 1
Explanation:
The only possible stable binary array is [1,0,1].
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 <= 1000In #3130 Find All Possible Stable Binary Arrays II, we must count binary arrays containing a fixed number of 0s and 1s such that no more than limit identical elements appear consecutively. A direct brute-force construction is infeasible due to the exponential number of arrays, so the problem is best handled using dynamic programming.
Define DP states that track how many 0s and 1s have been used and whether the current array ends with a 0 or 1. The challenge is efficiently enforcing the consecutive limit. Instead of iterating over all possible previous segment lengths, we use prefix sums to aggregate valid transitions where the previous run length does not exceed limit. This reduces repeated summation when extending arrays with another digit.
The DP transitions compute the number of ways to end with 0 or 1 while respecting both the remaining counts and the stability constraint. With prefix-sum optimization, the overall complexity becomes manageable for large inputs.
Time Complexity: approximately O(zero × one). Space Complexity: O(zero × one) for the DP tables.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Prefix Sum Optimization | O(zero × one) | O(zero × one) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Let <code>dp[x][y][z = 0/1]</code> be the number of stable arrays with exactly <code>x</code> zeros, <code>y</code> ones, and the last element is <code>z</code>. (0 or 1). <code>dp[x][y][0] + dp[x][y][1]</code> is the answer for given <code>(x, y)</code>.
If we have already placed <code>x</code> 1 and <code>y</code> 0, if we place a group of <code>k</code> 0, the number of ways is <code>dp[x-k][y][1]</code>. We can place a group with size <code>i</code>, where <code>i</code> varies from 1 to <code>min(limit, zero - x)</code>. Similarly, we can solve by placing a group of ones.
Speed up the calculation using prefix arrays to store the sum of <code>dp</code> states.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Prefix sums help aggregate ranges of valid DP states instead of iterating through all possible previous segment lengths. This significantly reduces repeated computations and keeps the transition time efficient.
Problems involving constrained binary sequences and dynamic programming patterns are common in FAANG-style interviews. While this exact problem may not always appear, similar DP and prefix-sum optimization techniques are frequently tested.
The optimal approach uses dynamic programming with prefix sum optimization. DP tracks how many zeros and ones are used and whether the array ends with 0 or 1, while prefix sums efficiently enforce the maximum consecutive limit constraint.
The solution mainly relies on 2D dynamic programming arrays along with auxiliary prefix sum arrays. These structures allow efficient state transitions while respecting both count constraints and consecutive limits.