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 exactlyzero.
  • 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 10^9 + 7.

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

Solution

Method 1 – Dynamic Programming (DP with Last Placed Value)

Intuition

We want to count all binary arrays with exactly zero 0s and one 1s, such that no subarray of length > limit is all 0s or all 1s. This means we cannot have more than limit consecutive 0s or 1s. We can use DP to count the number of ways to build such arrays, keeping track of the last value placed and how many consecutive times it has been placed.

Approach

  1. Define dp(z, o, last, cnt) as the number of ways to arrange z zeros and o ones, where the last placed value is last (0 or 1), and it has been placed cnt times consecutively.
  2. Base case: if z == 0 and o == 0, return 1.
  3. If last placed is 0 and z > 0 and cnt < limit, we can place another 0.
  4. If last placed is 1 and o > 0 and cnt < limit, we can place another 1.
  5. We can always switch to the other value if available, resetting the count to 1.
  6. Use memoization to avoid recomputation.
  7. Try both starting with 0 and starting with 1, sum the results.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int mod = 1e9+7;
    int dp(int z, int o, int last, int cnt, int limit, vector<vector<vector<vector<int>>>>& memo) {
        if (z == 0 && o == 0) return 1;
        if (memo[z][o][last][cnt] != -1) return memo[z][o][last][cnt];
        int ans = 0;
        if (last == 0) {
            if (z > 0 && cnt < limit) ans = (ans + dp(z-1, o, 0, cnt+1, limit, memo)) % mod;
            if (o > 0) ans = (ans + dp(z, o-1, 1, 1, limit, memo)) % mod;
        } else {
            if (o > 0 && cnt < limit) ans = (ans + dp(z, o-1, 1, cnt+1, limit, memo)) % mod;
            if (z > 0) ans = (ans + dp(z-1, o, 0, 1, limit, memo)) % mod;
        }
        return memo[z][o][last][cnt] = ans;
    }
    int stableArrays(int zero, int one, int limit) {
        vector<vector<vector<vector<int>>>> memo(zero+1, vector<vector<vector<int>>>(one+1, vector<vector<int>>(2, vector<int>(limit+2, -1))));
        int ans = 0;
        if (zero > 0) ans = (ans + dp(zero-1, one, 0, 1, limit, memo)) % mod;
        if (one > 0) ans = (ans + dp(zero, one-1, 1, 1, limit, memo)) % mod;
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func stableArrays(zero, one, limit int) int {
    mod := int(1e9+7)
    memo := make(map[[4]int]int)
    var dp func(z, o, last, cnt int) int
    dp = func(z, o, last, cnt int) int {
        if z == 0 && o == 0 { return 1 }
        key := [4]int{z, o, last, cnt}
        if v, ok := memo[key]; ok { return v }
        ans := 0
        if last == 0 {
            if z > 0 && cnt < limit { ans = (ans + dp(z-1, o, 0, cnt+1)) % mod }
            if o > 0 { ans = (ans + dp(z, o-1, 1, 1)) % mod }
        } else {
            if o > 0 && cnt < limit { ans = (ans + dp(z, o-1, 1, cnt+1)) % mod }
            if z > 0 { ans = (ans + dp(z-1, o, 0, 1)) % mod }
        }
        memo[key] = ans
        return ans
    }
    ans := 0
    if zero > 0 { ans = (ans + dp(zero-1, one, 0, 1)) % mod }
    if one > 0 { ans = (ans + dp(zero, one-1, 1, 1)) % mod }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    int mod = (int)1e9+7;
    Integer[][][][] memo;
    int dp(int z, int o, int last, int cnt, int limit) {
        if (z == 0 && o == 0) return 1;
        if (memo[z][o][last][cnt] != null) return memo[z][o][last][cnt];
        int ans = 0;
        if (last == 0) {
            if (z > 0 && cnt < limit) ans = (ans + dp(z-1, o, 0, cnt+1, limit)) % mod;
            if (o > 0) ans = (ans + dp(z, o-1, 1, 1, limit)) % mod;
        } else {
            if (o > 0 && cnt < limit) ans = (ans + dp(z, o-1, 1, cnt+1, limit)) % mod;
            if (z > 0) ans = (ans + dp(z-1, o, 0, 1, limit)) % mod;
        }
        return memo[z][o][last][cnt] = ans;
    }
    public int stableArrays(int zero, int one, int limit) {
        memo = new Integer[zero+1][one+1][2][limit+2];
        int ans = 0;
        if (zero > 0) ans = (ans + dp(zero-1, one, 0, 1, limit)) % mod;
        if (one > 0) ans = (ans + dp(zero, one-1, 1, 1, limit)) % mod;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun stableArrays(zero: Int, one: Int, limit: Int): Int {
        val mod = 1_000_000_007
        val memo = mutableMapOf<List<Int>, Int>()
        fun dp(z: Int, o: Int, last: Int, cnt: Int): Int {
            if (z == 0 && o == 0) return 1
            val key = listOf(z, o, last, cnt)
            memo[key]?.let { return it }
            var ans = 0
            if (last == 0) {
                if (z > 0 && cnt < limit) ans = (ans + dp(z-1, o, 0, cnt+1)) % mod
                if (o > 0) ans = (ans + dp(z, o-1, 1, 1)) % mod
            } else {
                if (o > 0 && cnt < limit) ans = (ans + dp(z, o-1, 1, cnt+1)) % mod
                if (z > 0) ans = (ans + dp(z-1, o, 0, 1)) % mod
            }
            memo[key] = ans
            return ans
        }
        var ans = 0
        if (zero > 0) ans = (ans + dp(zero-1, one, 0, 1)) % mod
        if (one > 0) ans = (ans + dp(zero, one-1, 1, 1)) % mod
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution:
    def stableArrays(self, zero: int, one: int, limit: int) -> int:
        from functools import lru_cache
        MOD = 10**9 + 7
        @lru_cache(maxsize=None)
        def dp(z: int, o: int, last: int, cnt: int) -> int:
            if z == 0 and o == 0:
                return 1
            ans = 0
            if last == 0:
                if z > 0 and cnt < limit:
                    ans = (ans + dp(z-1, o, 0, cnt+1)) % MOD
                if o > 0:
                    ans = (ans + dp(z, o-1, 1, 1)) % MOD
            else:
                if o > 0 and cnt < limit:
                    ans = (ans + dp(z, o-1, 1, cnt+1)) % MOD
                if z > 0:
                    ans = (ans + dp(z-1, o, 0, 1)) % MOD
            return ans
        ans = 0
        if zero > 0:
            ans = (ans + dp(zero-1, one, 0, 1)) % MOD
        if one > 0:
            ans = (ans + dp(zero, one-1, 1, 1)) % MOD
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

use std::collections::HashMap;
impl Solution {
    pub fn stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
        fn dp(z: i32, o: i32, last: i32, cnt: i32, limit: i32, memo: &mut HashMap<(i32,i32,i32,i32), i32>) -> i32 {
            if z == 0 && o == 0 { return 1; }
            if let Some(&v) = memo.get(&(z,o,last,cnt)) { return v; }
            let mut ans = 0;
            let m = 1_000_000_007;
            if last == 0 {
                if z > 0 && cnt < limit { ans = (ans + dp(z-1, o, 0, cnt+1, limit, memo)) % m; }
                if o > 0 { ans = (ans + dp(z, o-1, 1, 1, limit, memo)) % m; }
            } else {
                if o > 0 && cnt < limit { ans = (ans + dp(z, o-1, 1, cnt+1, limit, memo)) % m; }
                if z > 0 { ans = (ans + dp(z-1, o, 0, 1, limit, memo)) % m; }
            }
            memo.insert((z,o,last,cnt), ans);
            ans
        }
        let mut memo = HashMap::new();
        let mut ans = 0;
        if zero > 0 { ans = (ans + dp(zero-1, one, 0, 1, limit, &mut memo)) % 1_000_000_007; }
        if one > 0 { ans = (ans + dp(zero, one-1, 1, 1, limit, &mut memo)) % 1_000_000_007; }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    stableArrays(zero: number, one: number, limit: number): number {
        const MOD = 1e9 + 7;
        const memo = new Map<string, number>();
        function dp(z: number, o: number, last: number, cnt: number): number {
            if (z === 0 && o === 0) return 1;
            const key = `${z},${o},${last},${cnt}`;
            if (memo.has(key)) return memo.get(key)!;
            let ans = 0;
            if (last === 0) {
                if (z > 0 && cnt < limit) ans = (ans + dp(z-1, o, 0, cnt+1)) % MOD;
                if (o > 0) ans = (ans + dp(z, o-1, 1, 1)) % MOD;
            } else {
                if (o > 0 && cnt < limit) ans = (ans + dp(z, o-1, 1, cnt+1)) % MOD;
                if (z > 0) ans = (ans + dp(z-1, o, 0, 1)) % MOD;
            }
            memo.set(key, ans);
            return ans;
        }
        let ans = 0;
        if (zero > 0) ans = (ans + dp(zero-1, one, 0, 1)) % MOD;
        if (one > 0) ans = (ans + dp(zero, one-1, 1, 1)) % MOD;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(zero * one * limit * 2), as each state is visited once.
  • 🧺 Space complexity: O(zero * one * limit * 2), for memoization.