Description
You are given 3 positive integers num_zeros, num_ones, and limit.
A binary array arr is called stable if:
- The number of occurrences of 0 in
arris exactlynum_zeros. - The number of occurrences of 1 in
arris exactlynum_ones. - Each subarray of
arrwith a size greater thanlimitmust contain at least one occurrence of both 0 and 1.
Return an integer denoting 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
Solutions
This solution uses dynamic programming to count arrays containing exactly zero zeros and one ones where no consecutive sequence of the same bit exceeds limit. The algorithm builds a 3D table dp[i][j][lastBit] tracking the number of valid arrays using i zeros, j ones, and ending with bit lastBit (0 or 1). For each state, it sums the ways from previous states ending with the same bit, then subtracts sequences that would violate the limit constraint using a sliding window approach. Finally, it returns the sum of both possibilities (ending in 0 or 1) after applying modulo arithmetic to keep numbers manageable.
/**
* @param {number} zero
* @param {number} one
* @param {number} limit
* @return {number}
*/
var numberOfStableArrays = function (zero, one, limit) {
const MOD = 1000000007;
let dp = Array.from({ length: zero + 1 }, () =>
Array.from({ length: one + 1 }, () => [0, 0]),
);
for (let i = 0; i <= zero; i++) {
for (let j = 0; j <= one; j++) {
for (let lastBit = 0; lastBit <= 1; lastBit++) {
if (i === 0) {
if (lastBit === 0 || j > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (j === 0) {
if (lastBit === 1 || i > limit) {
dp[i][j][lastBit] = 0;
} else {
dp[i][j][lastBit] = 1;
}
} else if (lastBit === 0) {
dp[i][j][lastBit] = dp[i - 1][j][0] + dp[i - 1][j][1];
if (i > limit) {
dp[i][j][lastBit] -= dp[i - limit - 1][j][1];
}
} else {
dp[i][j][lastBit] = dp[i][j - 1][0] + dp[i][j - 1][1];
if (j > limit) {
dp[i][j][lastBit] -= dp[i][j - limit - 1][0];
}
}
dp[i][j][lastBit] %= MOD;
if (dp[i][j][lastBit] < 0) {
dp[i][j][lastBit] += MOD;
}
}
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
};