LeetCode Problem Workspace
Find All Possible Stable Binary Arrays II
Compute the number of stable binary arrays using state transition dynamic programming with exact zero, one, and limit constraints.
2
Topics
5
Code langs
3
Related
Practice Focus
Hard · State transition dynamic programming
Answer-first summary
Compute the number of stable binary arrays using state transition dynamic programming with exact zero, one, and limit constraints.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for State transition dynamic programming
Use dynamic programming to track counts of stable arrays with exact numbers of zeros and ones. Represent the state as dp[x][y][z], where x and y are remaining zeros and ones, and z is the last element. Combine results from both ending states to find the total number of stable binary arrays within the limit.
Problem Statement
Given three positive integers zero, one, and limit, count all binary arrays that satisfy stability conditions. An array is stable if it contains at most limit consecutive zeros or ones and uses exactly zero zeros and one ones.
Return the total number of distinct stable binary arrays possible with these constraints. Arrays can vary in order but must respect the maximum consecutive limit and exact counts of zeros and ones.
Examples
Example 1
Input: zero = 1, one = 1, limit = 2
Output: 2
The two possible stable binary arrays are [1,0] and [0,1] .
Example 2
Input: zero = 1, one = 2, limit = 1
Output: 1
The only possible stable binary array is [1,0,1] .
Example 3
Input: zero = 3, one = 3, limit = 2
Output: 14
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 <= 1000
Solution Approach
Define DP State
Create dp[x][y][z] representing the number of stable arrays with x remaining zeros, y remaining ones, and last element z (0 or 1). This captures the exact counts and enforces the limit on consecutive elements.
State Transitions
For each state, append up to 'limit' zeros or ones if allowed. Update dp[x][y][0] from previous dp states ending with 1 and dp[x][y][1] from states ending with 0. Use prefix sums to efficiently sum contributions from multiple consecutive elements.
Compute Total
After filling dp for all counts, sum dp[0][0][0] and dp[0][0][1] to get the total number of stable arrays. This ensures all arrays use the exact number of zeros and ones and respect the consecutive limit.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time and space depend on zero, one, and limit values. Filling dp[x][y][z] for all combinations gives O(zero one limit) in naive form, optimized with prefix sums for practical performance.
What Interviewers Usually Probe
- Expecting recognition of state representation dp[x][y][z] for exact zero and one counts.
- Prefers seeing prefix sum optimization to handle consecutive limit efficiently.
- Looking for awareness of transition constraints when adding multiple zeros or ones at once.
Common Pitfalls or Variants
Common pitfalls
- Failing to enforce the consecutive limit correctly in DP transitions.
- Ignoring one ending state when summing total stable arrays, undercounting results.
- Incorrect indexing or off-by-one errors in prefix sums for multiple consecutive elements.
Follow-up variants
- Change the consecutive limit dynamically per element type.
- Count stable arrays without fixing exact numbers of zeros or ones.
- Generalize to ternary or higher base arrays with similar stability constraints.
FAQ
What is a stable binary array in this problem?
A stable binary array has at most 'limit' consecutive zeros or ones and uses exactly the given counts of zeros and ones.
How does the state transition DP work here?
Each dp[x][y][z] counts arrays with x zeros, y ones remaining, and last element z, updating by adding up to 'limit' consecutive zeros or ones from opposite ending states.
Can this approach handle large zero and one values efficiently?
Yes, using prefix sums reduces repeated summation in transitions, making it feasible for large counts within constraints.
Are all permutations of zeros and ones considered?
Only permutations respecting the consecutive limit and exact counts of zeros and ones are included in the total.
Does GhostInterview provide ready-made solution checks?
Yes, it verifies the DP transitions and total count against examples to prevent undercounting or misapplying the consecutive limit.
Solution
Solution 1: Memoization Search
We design a function $dfs(i, j, k)$ to represent the number of stable binary arrays that satisfy the problem conditions when there are $i$ $0$s and $j$ $1$s left, and the next number to be filled is $k$. The answer is $dfs(zero, one, 0) + dfs(zero, one, 1)$.
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if i == 0:
return int(k == 1 and j <= limit)
if j == 0:
return int(k == 0 and i <= limit)
if k == 0:
return (
dfs(i - 1, j, 0)
+ dfs(i - 1, j, 1)
- (0 if i - limit - 1 < 0 else dfs(i - limit - 1, j, 1))
)
return (
dfs(i, j - 1, 0)
+ dfs(i, j - 1, 1)
- (0 if j - limit - 1 < 0 else dfs(i, j - limit - 1, 0))
)
mod = 10**9 + 7
ans = (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
dfs.cache_clear()
return ansSolution 2: Dynamic Programming
We can also convert the memoization search of Solution 1 into dynamic programming.
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if i == 0:
return int(k == 1 and j <= limit)
if j == 0:
return int(k == 0 and i <= limit)
if k == 0:
return (
dfs(i - 1, j, 0)
+ dfs(i - 1, j, 1)
- (0 if i - limit - 1 < 0 else dfs(i - limit - 1, j, 1))
)
return (
dfs(i, j - 1, 0)
+ dfs(i, j - 1, 1)
- (0 if j - limit - 1 < 0 else dfs(i, j - limit - 1, 0))
)
mod = 10**9 + 7
ans = (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
dfs.cache_clear()
return ansContinue Topic
dynamic programming
Practice more edge cases under the same topic.
arrow_forwardauto_awesomeContinue Pattern
State transition dynamic programming
Expand the same solving frame across more problems.
arrow_forwardsignal_cellular_altSame Difficulty Track
Hard
Stay on this level to stabilize interview delivery.
arrow_forward