# Find All Possible Stable Binary Arrays II
**Difficulty:** HARD
[External](https://leetcode.com/problems/find-all-possible-stable-binary-arrays-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-all-possible-stable-binary-arrays-ii
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Companies:** [IBM](https://scaleengineer.com/companies/ibm)
---
## 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]`.

**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
## Naive Dynamic Programming
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`.
**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.
**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.
### Explanation
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.

```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 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);
    }
}
```
### Algorithm
1. Define a 3D DP table `dp[i][j][k]`, where `dp[i][j][0]` is the number of stable arrays with `i` zeros and `j` ones ending in a block of zeros, and `dp[i][j][1]` is for arrays ending in a block of ones.
2. Establish the recurrence relations:
   - To form an array ending in a block of `k` zeros (`1 <= k <= limit`), we must append it to an array with `i-k` zeros and `j` ones 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]`.
3. 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] = 1` for `1 <= k <= limit`, and `dp[0][k][1] = 1` for `1 <= k <= limit`.
4. Iterate through `i` from 1 to `zero` and `j` from 1 to `one`, filling the DP table. For each `(i, j)`, compute `dp[i][j][0]` and `dp[i][j][1]` by iterating `k` up to `limit` to calculate the sums.
5. 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`.

## DP with Prefix Sums Optimization
The naive DP approach is too slow due to the repeated summation in the inner loop. This can be optimized. The sum required for each DP state calculation is over a contiguous range of previous states. This pattern is known as a sliding window sum and can be computed in O(1) time using prefix sums.
**Time:** O(zero * one). We iterate through the `(zero + 1) x (one + 1)` grid, and each DP state is computed in O(1) time. · **Space:** O(zero * one) for the DP table and two prefix sum tables.
**Pros:** Highly efficient time complexity, well within the limits for the given constraints.; The use of prefix sums is a standard and powerful optimization technique for this class of DP problems.
**Cons:** Requires more memory due to the additional prefix sum tables, although the overall space complexity remains O(zero * one).
### Explanation
We maintain the same DP state `dp[i][j][k]` but optimize the calculation. Instead of re-computing the sum every time, we maintain two auxiliary prefix sum tables: `prefix0` and `prefix1`.
- `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 tables, the sum `sum_{k=1 to limit} dp[i-k][j][1]` can be found by `prefix1[i-1][j] - prefix1[i-limit-1][j]`. This reduces the time to calculate each DP state to O(1).

To handle the base cases elegantly, we can introduce a sentinel value for an empty array. We set `dp[0][0][0] = 1` and `dp[0][0][1] = 1`. This represents an empty prefix, which can be thought of as ending in either a 0 or a 1 for the purpose of starting a new block. For instance, the number of ways to form an array of `k` zeros is `sum_{l=1 to k} dp[k-l][0][1]`. Since `dp[i>0][0][1]` is 0, this sum correctly evaluates to `dp[0][0][1] = 1`.

We iterate through `i` and `j`, compute `dp[i][j][0]` and `dp[i][j][1]` using the prefix sums, and then update the prefix sum tables with these new values. This brings the total time complexity down significantly.

```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];
        // prefix0[i][j] = sum of dp[i][k][0] for k from 0 to j
        long[][] prefix0 = new long[zero + 1][one + 1];
        // prefix1[i][j] = sum of dp[k][j][1] for k from 0 to i
        long[][] prefix1 = new long[zero + 1][one + 1];

        // Sentinel values for an empty prefix
        dp[0][0][0] = 1;
        dp[0][0][1] = 1;
        prefix0[0][0] = 1;
        prefix1[0][0] = 1;

        for (int i = 0; i <= zero; i++) {
            for (int j = 0; j <= one; j++) {
                if (i == 0 && j == 0) {
                    continue;
                }

                // Calculate dp[i][j][0]: ways to form with i zeros, j ones, ending in a block of 0s
                if (i > 0) {
                    long sum_prev_1s = (prefix1[i - 1][j] - (i - limit - 1 >= 0 ? prefix1[i - limit - 1][j] : 0) + MOD) % MOD;
                    dp[i][j][0] = sum_prev_1s;
                }

                // Calculate dp[i][j][1]: ways to form with i zeros, j ones, ending in a block of 1s
                if (j > 0) {
                    long sum_prev_0s = (prefix0[i][j - 1] - (j - limit - 1 >= 0 ? prefix0[i][j - limit - 1] : 0) + MOD) % MOD;
                    dp[i][j][1] = sum_prev_0s;
                }
                
                // Update prefix sums for the current (i, j)
                prefix0[i][j] = ((j > 0 ? prefix0[i][j - 1] : 0) + dp[i][j][0]) % MOD;
                prefix1[i][j] = ((i > 0 ? prefix1[i - 1][j] : 0) + dp[i][j][1]) % MOD;
            }
        }

        return (int)((dp[zero][one][0] + dp[zero][one][1]) % MOD);
    }
}
```
### Algorithm
1. Use the same DP state `dp[i][j][k]` as the naive approach.
2. Observe that the summations in the recurrences are over a sliding window. This allows for an O(1) transition.
   - `sum_{k=1 to limit} dp[i-k][j][1]` can be computed from `sum_{k=1 to limit} dp[i-1-k][j][1]` by adding one term and removing another.
3. To implement this efficiently, we use prefix sum tables. Let `prefix0[i][j] = sum_{k=0 to j} dp[i][k][0]` and `prefix1[i][j] = sum_{k=0 to i} dp[k][j][1]`.
4. The recurrences are transformed:
   - `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`
5. To simplify base cases, we use a sentinel value. We define `dp[0][0][0] = 1` and `dp[0][0][1] = 1`, representing an empty prefix that can precede any block. This allows the recurrence to handle the initial blocks correctly.
6. Iterate `i` from 0 to `zero` and `j` from 0 to `one`. In each step, calculate `dp[i][j][0]` and `dp[i][j][1]` using the prefix sum tables, and then update the prefix sum tables for the current `(i, j)`.
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

```