Find All Possible Stable Binary Arrays I

Medium
1493.

Find All Possible Stable Binary Arrays I

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.

A binary array arr is stable when:

  • it contains exactly zero zeros and exactly one ones, and
  • every subarray longer than limit contains both a 0 and a 1 — in other words, no run of equal values is longer than limit.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} zero
 * @param {number} one
 * @param {number} limit
 * @return {number}
 */
var numberOfStableArrays = function(zero, one, limit) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

Problem statement

A binary array arr is stable when:

  • it contains exactly zero zeros and exactly one ones, and
  • every subarray longer than limit contains both a 0 and a 1 — in other words, no run of equal values is longer than limit.

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

  1. 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.

  2. Hint 2

    Let dp[i][j][0] count arrays with i zeros and j ones ending in 0 (similarly [1]). Appending a 0 to anything with i - 1 zeros gives dp[i-1][j][0] + dp[i-1][j][1].

  3. Hint 3

    That over-counts arrays ending in a run of limit + 1 zeros; those are exactly dp[i-limit-1][j][1] followed by limit + 1 zeros — 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

  1. Bases: dp[i][0][0] = 1 for 1 <= i <= limit (all zeros), dp[0][j][1] = 1 for 1 <= j <= limit; everything else on the axes is 0.
  2. 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).
  3. Symmetrically dp[i][j][1] = dp[i][j-1][0] + dp[i][j-1][1] - (j > limit ? dp[i][j-limit-1][0] : 0).
  4. Work modulo 10^9 + 7, adding the modulus before reducing a difference; return dp[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 than limit is 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]) % MOD

Java

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