Find All Possible Stable Binary Arrays II
HardPrompt
You are given 3 positive integers zero, one, and limit.
A binary array arr is called stable if:
- The number of occurrences of 0 in
arris exactlyzero. - The number of occurrences of 1 in
arris exactlyone. - Each subarray of
arrwith a size greater thanlimitmust 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 <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a straightforward dynamic programming solution. We define a DP state dp[i][j][k] to represent the number of stable arrays that can be formed using i zeros and j ones, where the array's last block of identical numbers is of type k (0 for zeros, 1 for ones). The key idea is that any stable array is formed by alternating blocks of 0s and 1s, with each block's length not exceeding limit.
Algorithm
- Define a 3D DP table
dp[i][j][k], wheredp[i][j][0]is the number of stable arrays withizeros andjones ending in a block of zeros, anddp[i][j][1]is for arrays ending in a block of ones. - Establish the recurrence relations:
- To form an array ending in a block of
kzeros (1 <= k <= limit), we must append it to an array withi-kzeros andjones that ends in a block of ones. Thus,dp[i][j][0] = sum_{k=1 to min(i, limit)} dp[i-k][j][1]. - Similarly,
dp[i][j][1] = sum_{k=1 to min(j, limit)} dp[i][j-k][0].
- To form an array ending in a block of
- Initialize base cases: For an array with only one type of element, there's only one way to arrange them in a single block. So,
dp[k][0][0] = 1for1 <= k <= limit, anddp[0][k][1] = 1for1 <= k <= limit. - Iterate through
ifrom 1 tozeroandjfrom 1 toone, filling the DP table. For each(i, j), computedp[i][j][0]anddp[i][j][1]by iteratingkup tolimitto calculate the sums. - The final answer is the sum of arrays ending in a block of zeros and those ending in a block of ones:
(dp[zero][one][0] + dp[zero][one][1]) % MOD.
Walkthrough
We build a 3D DP table, dp[zero+1][one+1][2]. The state dp[i][j][0] counts the number of stable arrays using i zeros and j ones that end with a block of zeros. Symmetrically, dp[i][j][1] counts arrays ending with a block of ones.
To compute dp[i][j][0], we consider appending a block of k zeros (where 1 <= k <= limit) to a valid array. This previous array must have had i-k zeros and j ones, and it must have ended with a block of ones to allow a new block of zeros to start. Therefore, we sum up dp[i-k][j][1] for all possible k values. A similar logic applies to dp[i][j][1].
The base cases are arrays composed of only one type of number. For example, an array of k zeros (1 <= k <= limit) is valid, so dp[k][0][0] = 1.
We then fill the DP table by iterating through all counts of zeros and ones up to the required amounts. The final result is the sum of all stable arrays with zero zeros and one ones, regardless of what they end with.
class Solution { public int numberOfStableArrays(int zero, int one, int limit) { int MOD = 1_000_000_007; long[][][] dp = new long[zero + 1][one + 1][2]; // Base cases: arrays with only 0s or only 1s for (int k = 1; k <= Math.min(zero, limit); k++) { dp[k][0][0] = 1; } for (int k = 1; k <= Math.min(one, limit); k++) { dp[0][k][1] = 1; } for (int i = 1; i <= zero; i++) { for (int j = 1; j <= one; j++) { // Calculate dp[i][j][0] long sum1 = 0; for (int k = 1; k <= Math.min(i, limit); k++) { sum1 = (sum1 + dp[i - k][j][1]) % MOD; } dp[i][j][0] = sum1; // Calculate dp[i][j][1] long sum0 = 0; for (int k = 1; k <= Math.min(j, limit); k++) { sum0 = (sum0 + dp[i][j - k][0]) % MOD; } dp[i][j][1] = sum0; } } return (int) ((dp[zero][one][0] + dp[zero][one][1]) % MOD); }}Complexity
Time
O(zero * one * limit). We have nested loops for `i` and `j`, and inside them, another loop for `k` up to `limit`. Given constraints up to 1000, this is approximately 1000*1000*1000 = 10^9 operations, which is too slow.
Space
O(zero * one) to store the DP table.
Trade-offs
Pros
The logic is a direct translation of the combinatorial structure of the problem, making it easy to understand.
Cons
The time complexity is too high for the given constraints and will result in a Time Limit Exceeded error.
Solutions
Solution
class Solution {private final int mod = (int)1 e9 + 7;private Long[][][] f;private int limit;public int numberOfStableArrays(int zero, int one, int limit) { f = new Long[zero + 1][one + 1][2]; this.limit = limit; return (int)((dfs(zero, one, 0) + dfs(zero, one, 1)) % mod); }private long dfs(int i, int j, int k) { if (i < 0 || j < 0) { return 0; } if (i == 0) { return k == 1 && j <= limit ? 1 : 0; } if (j == 0) { return k == 0 && i <= limit ? 1 : 0; } if (f[i][j][k] != null) { return f[i][j][k]; } if (k == 0) { f[i][j][k] = (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - dfs(i - limit - 1, j, 1) + mod) % mod; } else { f[i][j][k] = (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - dfs(i, j - limit - 1, 0) + mod) % mod; } return f[i][j][k]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.