Find All Possible Stable Binary Arrays I — Solution
Find All Possible Stable Binary Arrays I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find All Possible Stable Binary Arrays I is a medium coding problem on dynamic programming, prefix sum and combinatorics, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Prefix Sum, Combinatorics
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A binary array arr is stable when:
- it contains exactly
zerozeros and exactlyoneones, and - every subarray longer than
limitcontains both a0and a1— in other words, no run of equal values is longer thanlimit.
Return the number of stable binary arrays, modulo 10^9 + 7.
Example 1
Input: zero = 1, one = 1, limit = 2
Output: 2
Explanation: `[0,1]` and `[1,0]`.
Example 2
Input: zero = 1, one = 2, limit = 1
Output: 1
Explanation: Only `[1,0,1]` — `[1,1,0]` and `[0,1,1]` have a run of two ones.
Example 3
Input: zero = 3, one = 3, limit = 2
Output: 14
Constraints
1 <= zero, one, limit <= 200
Hints for Find All Possible Stable Binary Arrays I
Hint 1
Build the array left to right; you need to know how many zeros and ones you have used and what the last value was.
Hint 2
Let
dp[i][j][0]count arrays withizeros andjones ending in0(similarly[1]). Appending a0to anything withi - 1zeros givesdp[i-1][j][0] + dp[i-1][j][1].Hint 3
That over-counts arrays ending in a run of
limit + 1zeros; those are exactlydp[i-limit-1][j][1]followed bylimit + 1zeros — subtract them.
How to solve Find All Possible Stable Binary Arrays I
Count by (zeros used, ones used, last value). Appending one more 0 is always fine unless it creates a run of limit + 1 zeros, and the arrays where that happens are in bijection with arrays that ended in 1 exactly limit + 1 zeros earlier.
Approach
- Bases:
dp[i][0][0] = 1for1 <= i <= limit(all zeros),dp[0][j][1] = 1for1 <= j <= limit; everything else on the axes is 0. - For
i, j >= 1:dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1] - (i > limit ? dp[i-limit-1][j][1] : 0). - Symmetrically
dp[i][j][1] = dp[i][j-1][0] + dp[i][j-1][1] - (j > limit ? dp[i][j-limit-1][0] : 0). - Work modulo
10^9 + 7, adding the modulus before reducing a difference; returndp[zero][one][0] + dp[zero][one][1].
Why it works
Assume every count with fewer elements is exact. Appending 0 to a stable array with i - 1 zeros is stable unless the final zero run becomes limit + 1 long; such an extended array is a stable array with i - limit - 1 zeros ending in 1 (or, when i - limit - 1 = 0, the all-ones prefix counted on the axis) followed by limit + 1 zeros, so subtracting exactly those leaves the stable arrays ending in 0.
Complexity
- Time —
O(zero · one) - Space —
O(zero · one)
Pitfalls
- The subtracted term must come from the array that ends in the other value.
- Modular subtraction can go negative — add the modulus first.
- The axis bases stop at
limit: an all-zero array longer thanlimitis not stable.
Reference solution
Python
def numberOfStableArrays(zero: int, one: int, limit: int) -> int:
MOD = 10**9 + 7
d0 = [[0] * (one + 1) for _ in range(zero + 1)]
d1 = [[0] * (one + 1) for _ in range(zero + 1)]
for i in range(1, min(zero, limit) + 1):
d0[i][0] = 1
for j in range(1, min(one, limit) + 1):
d1[0][j] = 1
for i in range(1, zero + 1):
for j in range(1, one + 1):
a = d0[i - 1][j] + d1[i - 1][j]
if i > limit:
a -= d1[i - limit - 1][j]
b = d0[i][j - 1] + d1[i][j - 1]
if j > limit:
b -= d0[i][j - limit - 1]
d0[i][j] = a % MOD
d1[i][j] = b % MOD
return (d0[zero][one] + d1[zero][one]) % MODJava
public static int numberOfStableArrays(int zero, int one, int limit) {
final long MOD = 1000000007L;
long[][] d0 = new long[zero + 1][one + 1];
long[][] d1 = new long[zero + 1][one + 1];
for (int i = 1; i <= Math.min(zero, limit); i++) d0[i][0] = 1;
for (int j = 1; j <= Math.min(one, limit); j++) d1[0][j] = 1;
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
long a = d0[i - 1][j] + d1[i - 1][j];
if (i > limit) a += MOD - d1[i - limit - 1][j];
long b = d0[i][j - 1] + d1[i][j - 1];
if (j > limit) b += MOD - d0[i][j - limit - 1];
d0[i][j] = a % MOD;
d1[i][j] = b % MOD;
}
}
return (int) ((d0[zero][one] + d1[zero][one]) % MOD);
}C++
int numberOfStableArrays(int zero, int one, int limit) {
const long long MOD = 1000000007LL;
vector<vector<long long>> d0(zero + 1, vector<long long>(one + 1, 0));
vector<vector<long long>> d1(zero + 1, vector<long long>(one + 1, 0));
for (int i = 1; i <= min(zero, limit); i++) d0[i][0] = 1;
for (int j = 1; j <= min(one, limit); j++) d1[0][j] = 1;
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
long long a = d0[i - 1][j] + d1[i - 1][j];
if (i > limit) a += MOD - d1[i - limit - 1][j];
long long b = d0[i][j - 1] + d1[i][j - 1];
if (j > limit) b += MOD - d0[i][j - limit - 1];
d0[i][j] = a % MOD;
d1[i][j] = b % MOD;
}
}
return (int) ((d0[zero][one] + d1[zero][one]) % MOD);
}JavaScript
var numberOfStableArrays = function(zero, one, limit) {
var MOD = 1000000007;
var d0 = [], d1 = [];
for (var i = 0; i <= zero; i++) {
d0.push(new Array(one + 1).fill(0));
d1.push(new Array(one + 1).fill(0));
}
for (i = 1; i <= Math.min(zero, limit); i++) d0[i][0] = 1;
for (var j = 1; j <= Math.min(one, limit); j++) d1[0][j] = 1;
for (i = 1; i <= zero; i++) {
for (j = 1; j <= one; j++) {
var a = d0[i - 1][j] + d1[i - 1][j];
if (i > limit) a += MOD - d1[i - limit - 1][j];
var b = d0[i][j - 1] + d1[i][j - 1];
if (j > limit) b += MOD - d0[i][j - limit - 1];
d0[i][j] = a % MOD;
d1[i][j] = b % MOD;
}
}
return (d0[zero][one] + d1[zero][one]) % MOD;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Prefix Sum