# Find All Possible Stable Binary Arrays I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-all-possible-stable-binary-arrays-i)
Canonical: https://scaleengineer.com/dsa/problems/find-all-possible-stable-binary-arrays-i
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
---
## Problem
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 `arr` is **exactly** `zero`.
* The number of occurrences of 1 in `arr` is **exactly** `one`.
* Each subarray of `arr` with a size greater than `limit` must 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]`, as both arrays have a single 0 and a single 1, and no subarray has a length greater than 2.

**Example 2:**

**Input:** zero = 1, one = 2, limit = 1

**Output:** 1

**Explanation:**

The only possible stable binary array is `[1,0,1]`.

Note that the binary arrays `[1,1,0]` and `[0,1,1]` have subarrays of length 2 with identical elements, hence, they are not stable.

**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 <= 200`

# Approaches
## 3D Dynamic Programming
This problem can be solved using dynamic programming. We build the stable arrays by adding one element at a time, keeping track of the number of zeros and ones used, and what the last element was. This helps us enforce the `limit` constraint on consecutive identical elements.
**Time:** O(zero * one * limit). We have nested loops for `i` (up to `zero`), `j` (up to `one`), and an inner summation loop `k` (up to `limit`). · **Space:** O(zero * one). We use a 3D DP table of size `(zero + 1) x (one + 1) x 2`.
**Pros:** Relatively straightforward to conceptualize from the problem definition.
**Cons:** The time complexity might be too high for larger constraints, although it might pass for the given constraints.
### Explanation
A straightforward dynamic programming approach involves defining a state that captures the necessary information to build a valid array. The state should include the number of zeros used, the number of ones used, and the last element added to the array.

Let `dp[i][j][0]` be the number of stable binary arrays using `i` zeros and `j` ones that end with a '0'.
Let `dp[i][j][1]` be the number of stable binary arrays using `i` zeros and `j` ones that end with a '1'.

To compute `dp[i][j][0]`, we consider how such an array could be formed. It must end with a block of `k` zeros, where `1 <= k <= limit`. This block must be appended to a valid array of `i-k` zeros and `j` ones that ends with a '1'. Thus, we sum up the possibilities over all valid `k`.

`dp[i][j][0] = (dp[i-1][j][1] + dp[i-2][j][1] + ... + dp[i-min(i, limit)][j][1]) % MOD`

Similarly, for `dp[i][j][1]`:

`dp[i][j][1] = (dp[i][j-1][0] + dp[i][j-2][0] + ... + dp[i][j-min(j, limit)][0]) % MOD`

The base cases are arrays that consist of only one type of element. An array of `k` zeros (with `1 <= k <= limit`) is a valid base case, as is an array of `k` ones.

We can then fill the DP table iteratively. The final answer is the sum of ways to form an array with `zero` zeros and `one` ones, ending in either '0' or '1'.

```java
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 consisting of only 0s or only 1s
        for (int i = 1; i <= Math.min(zero, limit); i++) {
            dp[i][0][0] = 1;
        }
        for (int j = 1; j <= Math.min(one, limit); j++) {
            dp[0][j][1] = 1;
        }

        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                // Calculate dp[i][j][0]: ends with 0
                // This is formed by appending k zeros to an array ending in 1.
                // Sum up dp[i-k][j][1] for k from 1 to limit.
                for (int k = 1; k <= Math.min(i, limit); k++) {
                    dp[i][j][0] = (dp[i][j][0] + dp[i - k][j][1]) % MOD;
                }

                // Calculate dp[i][j][1]: ends with 1
                // This is formed by appending k ones to an array ending in 0.
                // Sum up dp[i][j-k][0] for k from 1 to limit.
                for (int k = 1; k <= Math.min(j, limit); k++) {
                    dp[i][j][1] = (dp[i][j][1] + dp[i][j - k][0]) % MOD;
                }
            }
        }

        return (int) ((dp[zero][one][0] + dp[zero][one][1]) % MOD);
    }
}
```
### Algorithm
*   Let `dp[i][j][0]` be the number of stable binary arrays using `i` zeros and `j` ones that end with a '0'.
*   Let `dp[i][j][1]` be the number of stable binary arrays using `i` zeros and `j` ones that end with a '1'.
*   The state transitions are based on the idea that an array ending in a block of `k` identical elements must have been formed by appending that block to an array ending in the *opposite* element.
*   **Transition for `dp[i][j][0]`**: An array with `i` zeros and `j` ones ending in '0' must be formed by appending a block of `k` zeros (where `1 <= k <= limit`) to a valid array with `i-k` zeros and `j` ones that ends in '1'.
    ```
    dp[i][j][0] = sum(dp[i-k][j][1] for k in 1..min(i, limit))
    ```
*   **Transition for `dp[i][j][1]`**: Similarly, an array with `i` zeros and `j` ones ending in '1' is formed by appending a block of `k` ones (`1 <= k <= limit`) to a valid array with `i` zeros and `j-k` ones that ends in '0'.
    ```
    dp[i][j][1] = sum(dp[i][j-k][0] for k in 1..min(j, limit))
    ```
*   **Base Cases**: A block of `k` zeros can be a valid starting array, so `dp[k][0][0] = 1` for `1 <= k <= limit`. Similarly, `dp[0][k][1] = 1` for `1 <= k <= limit`.
*   **Algorithm Steps**:
    1.  Initialize a 3D DP table `dp[zero+1][one+1][2]` with zeros.
    2.  Set the base cases: `dp[k][0][0] = 1` for `1 <= k <= limit` and `dp[0][k][1] = 1` for `1 <= k <= limit`.
    3.  Iterate `i` from 1 to `zero` and `j` from 1 to `one`.
    4.  Inside the loops, calculate `dp[i][j][0]` and `dp[i][j][1]` using the transition formulas, which involve an inner loop up to `limit`. Remember to take modulo `10^9 + 7` at each addition.
    5.  The final answer is `(dp[zero][one][0] + dp[zero][one][1]) % MOD`.

## Optimized 3D DP with Prefix Sums
The previous DP approach involves a summation loop that can be optimized. The sums `sum(dp[i-k][j][1])` and `sum(dp[i][j-k][0])` are essentially sliding window sums. We can precompute these sums or calculate them in O(1) time using prefix sums, which significantly improves the time complexity.
**Time:** O(zero * one). We iterate through the `(zero+1) x (one+1)` grid, and each DP state is computed in O(1) using the prefix sum tables. · **Space:** O(zero * one). We use three tables (`dp`, `prefix0`, `prefix1`) of size proportional to `zero * one`.
**Pros:** Highly efficient and optimal in terms of time complexity.; Comfortably passes the given constraints.
**Cons:** Requires more space due to helper tables for prefix sums.; The logic is slightly more complex to derive and implement correctly.
### Explanation
The `O(zero * one * limit)` complexity of the naive DP approach comes from the inner loop used for summation. We can eliminate this loop by recognizing that the sum is over a contiguous range. This is a classic pattern that can be optimized using prefix sums or a sliding window technique.

Let's maintain two additional 2D arrays for prefix sums:
*   `prefix0[i][j]` will store the sum of `dp[i][k][0]` for `k` from 0 to `j`.
*   `prefix1[i][j]` will store the sum of `dp[k][j][1]` for `k` from 0 to `i`.

With these prefix sum tables, the transitions can be rewritten:

`dp[i][j][0] = (prefix1[i-1][j] - (i > limit ? prefix1[i-limit-1][j] : 0) + MOD) % MOD`
`dp[i][j][1] = (prefix0[i][j-1] - (j > limit ? prefix0[i][j-limit-1] : 0) + MOD) % MOD`

We iterate through `i` from 0 to `zero` and `j` from 0 to `one`. In each step `(i, j)`, we first calculate `dp[i][j][0]` and `dp[i][j][1]` using the pre-calculated prefix sums from previous steps. Then, we update the prefix sum tables `prefix0[i][j]` and `prefix1[i][j]` to include the new `dp` values, making them available for subsequent calculations. This reduces the computation for each state to constant time.

```java
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];
        long[][] prefix0 = new long[zero + 1][one + 1]; // prefix sum for dp[i][...][0] on j
        long[][] prefix1 = new long[zero + 1][one + 1]; // prefix sum for dp[...][j][1] on i

        // Base cases
        for (int i = 1; i <= Math.min(zero, limit); i++) {
            dp[i][0][0] = 1;
        }
        for (int j = 1; j <= Math.min(one, limit); j++) {
            dp[0][j][1] = 1;
        }

        // Initialize prefix sums for i=0 and j=0
        for (int i = 0; i <= zero; i++) {
            prefix1[i][0] = dp[i][0][1];
            if (i > 0) {
                prefix1[i][0] = (prefix1[i][0] + prefix1[i - 1][0]) % MOD;
            }
        }
        for (int j = 0; j <= one; j++) {
            prefix0[0][j] = dp[0][j][0];
            if (j > 0) {
                prefix0[0][j] = (prefix0[0][j] + prefix0[0][j - 1]) % MOD;
            }
        }

        // Fill DP table using prefix sums
        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                // Calculate dp[i][j][0]
                long ways_from_1s = (prefix1[i - 1][j] - (i - limit - 1 >= 0 ? prefix1[i - limit - 1][j] : 0) + MOD) % MOD;
                dp[i][j][0] = ways_from_1s;

                // Calculate dp[i][j][1]
                long ways_from_0s = (prefix0[i][j - 1] - (j - limit - 1 >= 0 ? prefix0[i][j - limit - 1] : 0) + MOD) % MOD;
                dp[i][j][1] = ways_from_0s;

                // Update prefix sums for the current state
                prefix0[i][j] = (prefix0[i][j - 1] + dp[i][j][0]) % MOD;
                prefix1[i][j] = (prefix1[i - 1][j] + dp[i][j][1]) % MOD;
            }
        }

        return (int) ((dp[zero][one][0] + dp[zero][one][1]) % MOD);
    }
}
```
### Algorithm
*   The DP state `dp[i][j][k]` remains the same as the naive approach.
*   The key observation is that the summations in the transitions are over a sliding window.
    *   `dp[i][j][0] = sum(dp[i-k][j][1] for k in 1..limit)`
    *   `dp[i][j][1] = sum(dp[i][j-k][0] for k in 1..limit)`
*   These sums can be computed in O(1) time using prefix sums.
*   Define `prefix0[i][j] = sum(dp[i][k][0] for k in 0..j)`.
*   Define `prefix1[i][j] = sum(dp[k][j][1] for k in 0..i)`.
*   The transitions become:
    *   `dp[i][j][0] = (prefix1[i-1][j] - prefix1[i-limit-1][j]) % MOD`
    *   `dp[i][j][1] = (prefix0[i][j-1] - prefix0[i][j-limit-1]) % MOD`
    (with appropriate boundary checks for negative indices).
*   **Algorithm Steps**:
    1.  Initialize `dp[zero+1][one+1][2]`, `prefix0[zero+1][one+1]`, and `prefix1[zero+1][one+1]` tables.
    2.  Set the same base cases as the naive approach: `dp[k][0][0] = 1` for `1 <= k <= limit` and `dp[0][k][1] = 1` for `1 <= k <= limit`.
    3.  Initialize the prefix sum tables for the base cases (i.e., for `i=0` and `j=0`).
    4.  Iterate `i` from 1 to `zero` and `j` from 1 to `one`.
    5.  Calculate `dp[i][j][0]` and `dp[i][j][1]` in O(1) time using the prefix sum tables.
    6.  Update the prefix sum tables `prefix0[i][j]` and `prefix1[i][j]` with the newly computed `dp` values.
    7.  The final answer is `(dp[zero][one][0] + dp[zero][one][1]) % MOD`.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
using ll = long long ; class Solution { public: int numberOfStableArrays ( int zero , int one , int limit ) { this -> limit = limit ; f = vector < vector < array < ll , 2 >>> ( zero + 1 , vector < array < ll , 2 >> ( one + 1 , { - 1 , - 1 })); return ( dfs ( zero , one , 0 ) + dfs ( zero , one , 1 )) % mod ; } private: const int mod = 1e9 + 7 ; int limit ; vector < vector < array < ll , 2 >>> f ; ll dfs ( int i , int j , int k ) { if ( i < 0 || j < 0 ) { return 0 ; } if ( i == 0 ) { return k == 1 && j <= limit ; } if ( j == 0 ) { return k == 0 && i <= limit ; } ll & res = f [ i ][ j ][ k ]; if ( res != - 1 ) { return res ; } if ( k == 0 ) { res = ( dfs ( i - 1 , j , 0 ) + dfs ( i - 1 , j , 1 ) - dfs ( i - limit - 1 , j , 1 ) + mod ) % mod ; } else { res = ( dfs ( i , j - 1 , 0 ) + dfs ( i , j - 1 , 1 ) - dfs ( i , j - limit - 1 , 0 ) + mod ) % mod ; } return res ; } };
```

### Python

```python
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 ans

```