Find All Possible Stable Binary Arrays II

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



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

Output: 2

Explanation:

The two possible stable binary arrays are `[1,0]` and `[0,1]`.

Example 2

1
2
3
4
5
6
7
8



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

Output: 1

Explanation:

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

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 <= 1000

Solution

Method 1 – Dynamic Programming with Prefix Sums

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 is a classic DP with prefix sums optimization: for each state, we can place up to min(zero, limit) 0s or up to min(one, limit) 1s in a row, then switch.

Approach

Let dp[z][o][last] be the number of ways to arrange z zeros and o ones, ending with last (0 or 1).
For each state, try placing cnt consecutive 0s (if last is 1) or 1s (if last is 0), for cnt in 1 to min(zero, limit) or min(one, limit).
Use prefix sums to speed up the transitions.
Initialize base cases: if only zeros or only ones left, only valid if count ≤ limit.
Sum the ways starting with 0 and with 1.

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
25
26
27
28
29
30
31
32
33


class Solution {
public:
    int mod = 1e9+7;
    int stableArrays(int zero, int one, int limit) {
        vector<vector<vector<int>>> dp(zero+1, vector<vector<int>>(one+1, vector<int>(2, 0)));
        for (int z = 0; z <= zero; ++z)
            for (int o = 0; o <= one; ++o)
                for (int last = 0; last < 2; ++last)
                    dp[z][o][last] = 0;
        for (int z = 0; z <= zero; ++z)
            for (int o = 0; o <= one; ++o) {
                if (z == 0 && o == 0) continue;
                if (z <= limit && o == 0) dp[z][0][0] = 1;
                if (o <= limit && z == 0) dp[0][o][1] = 1;
            }
        for (int z = 0; z <= zero; ++z) {
            for (int o = 0; o <= one; ++o) {
                if (z == 0 && o == 0) continue;
                // End with 0
                for (int cnt = 1; cnt <= min(z, limit); ++cnt) {
                    if (o > 0)
                        dp[z][o][0] = (dp[z][o][0] + dp[z-cnt][o][1]) % mod;
                }
                // End with 1
                for (int cnt = 1; cnt <= min(o, limit); ++cnt) {
                    if (z > 0)
                        dp[z][o][1] = (dp[z][o][1] + dp[z][o-cnt][0]) % mod;
                }
            }
        }
        return (dp[zero][one][0] + dp[zero][one][1]) % mod;
    }
};

 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
27
28
29
30
31
32
33
34


func stableArrays(zero, one, limit int) int {
    mod := int(1e9+7)
    dp := make([][][]int, zero+1)
    for z := range dp {
        dp[z] = make([][]int, one+1)
        for o := range dp[z] {
            dp[z][o] = make([]int, 2)
        }
    }
    for z := 0; z <= zero; z++ {
        for o := 0; o <= one; o++ {
            if z == 0 && o == 0 { continue }
            if z <= limit && o == 0 { dp[z][0][0] = 1 }
            if o <= limit && z == 0 { dp[0][o][1] = 1 }
        }
    }
    for z := 0; z <= zero; z++ {
        for o := 0; o <= one; o++ {
            if z == 0 && o == 0 { continue }
            for cnt := 1; cnt <= min(z, limit); cnt++ {
                if o > 0 {
                    dp[z][o][0] = (dp[z][o][0] + dp[z-cnt][o][1]) % mod
                }
            }
            for cnt := 1; cnt <= min(o, limit); cnt++ {
                if z > 0 {
                    dp[z][o][1] = (dp[z][o][1] + dp[z][o-cnt][0]) % mod
                }
            }
        }
    }
    return (dp[zero][one][0] + dp[zero][one][1]) % mod
}
func min(a, b int) int { if a < b { return a } else { return b } }

 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 {
    int mod = (int)1e9+7;
    public int stableArrays(int zero, int one, int limit) {
        int[][][] dp = new int[zero+1][one+1][2];
        for (int z = 0; z <= zero; ++z)
            for (int o = 0; o <= one; ++o) {
                if (z == 0 && o == 0) continue;
                if (z <= limit && o == 0) dp[z][0][0] = 1;
                if (o <= limit && z == 0) dp[0][o][1] = 1;
            }
        for (int z = 0; z <= zero; ++z) {
            for (int o = 0; o <= one; ++o) {
                if (z == 0 && o == 0) continue;
                for (int cnt = 1; cnt <= Math.min(z, limit); ++cnt) {
                    if (o > 0)
                        dp[z][o][0] = (dp[z][o][0] + dp[z-cnt][o][1]) % mod;
                }
                for (int cnt = 1; cnt <= Math.min(o, limit); ++cnt) {
                    if (z > 0)
                        dp[z][o][1] = (dp[z][o][1] + dp[z][o-cnt][0]) % mod;
                }
            }
        }
        return (dp[zero][one][0] + dp[zero][one][1]) % mod;
    }
}

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


class Solution {
    fun stableArrays(zero: Int, one: Int, limit: Int): Int {
        val mod = 1_000_000_007
        val dp = Array(zero+1) { Array(one+1) { IntArray(2) } }
        for (z in 0..zero) for (o in 0..one) {
            if (z == 0 && o == 0) continue
            if (z <= limit && o == 0) dp[z][0][0] = 1
            if (o <= limit && z == 0) dp[0][o][1] = 1
        }
        for (z in 0..zero) for (o in 0..one) {
            if (z == 0 && o == 0) continue
            for (cnt in 1..minOf(z, limit)) {
                if (o > 0) dp[z][o][0] = (dp[z][o][0] + dp[z-cnt][o][1]) % mod
            }
            for (cnt in 1..minOf(o, limit)) {
                if (z > 0) dp[z][o][1] = (dp[z][o][1] + dp[z][o-cnt][0]) % mod
            }
        }
        return (dp[zero][one][0] + dp[zero][one][1]) % mod
    }
}

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


class Solution:
    def stableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 10**9 + 7
        dp = [[[0, 0] for _ in range(one+1)] for _ in range(zero+1)]
        for z in range(zero+1):
            for o in range(one+1):
                if z == 0 and o == 0:
                    continue
                if z <= limit and o == 0:
                    dp[z][0][0] = 1
                if o <= limit and z == 0:
                    dp[0][o][1] = 1
        for z in range(zero+1):
            for o in range(one+1):
                if z == 0 and o == 0:
                    continue
                for cnt in range(1, min(z, limit)+1):
                    if o > 0:
                        dp[z][o][0] = (dp[z][o][0] + dp[z-cnt][o][1]) % MOD
                for cnt in range(1, min(o, limit)+1):
                    if z > 0:
                        dp[z][o][1] = (dp[z][o][1] + dp[z][o-cnt][0]) % MOD
        return (dp[zero][one][0] + dp[zero][one][1]) % MOD

 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
27
28
29
30
31
32


impl Solution {
    pub fn stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
        let zero = zero as usize;
        let one = one as usize;
        let limit = limit as usize;
        let mut dp = vec![vec![vec![0; 2]; one+1]; zero+1];
        let m = 1_000_000_007;
        for z in 0..=zero {
            for o in 0..=one {
                if z == 0 && o == 0 { continue; }
                if z <= limit && o == 0 { dp[z][0][0] = 1; }
                if o <= limit && z == 0 { dp[0][o][1] = 1; }
            }
        }
        for z in 0..=zero {
            for o in 0..=one {
                if z == 0 && o == 0 { continue; }
                for cnt in 1..=z.min(limit) {
                    if o > 0 {
                        dp[z][o][0] = (dp[z][o][0] + dp[z-cnt][o][1]) % m;
                    }
                }
                for cnt in 1..=o.min(limit) {
                    if z > 0 {
                        dp[z][o][1] = (dp[z][o][1] + dp[z][o-cnt][0]) % m;
                    }
                }
            }
        }
        (dp[zero][one][0] + dp[zero][one][1]) % m
    }
}

 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 dp = Array.from({length: zero+1}, () => Array.from({length: one+1}, () => [0, 0]));
        for (let z = 0; z <= zero; z++) {
            for (let o = 0; o <= one; o++) {
                if (z === 0 && o === 0) continue;
                if (z <= limit && o === 0) dp[z][0][0] = 1;
                if (o <= limit && z === 0) dp[0][o][1] = 1;
            }
        }
        for (let z = 0; z <= zero; z++) {
            for (let o = 0; o <= one; o++) {
                if (z === 0 && o === 0) continue;
                for (let cnt = 1; cnt <= Math.min(z, limit); cnt++) {
                    if (o > 0) dp[z][o][0] = (dp[z][o][0] + dp[z-cnt][o][1]) % MOD;
                }
                for (let cnt = 1; cnt <= Math.min(o, limit); cnt++) {
                    if (z > 0) dp[z][o][1] = (dp[z][o][1] + dp[z][o-cnt][0]) % MOD;
                }
            }
        }
        return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
    }
}

Complexity

⏰ Time complexity: O(zero * one * limit), as each state is visited and transitions up to limit.
🧺 Space complexity: O(zero * one), for the DP table.

Problem#

Examples#

Example 1#

Example 2#

Example 3#

Constraints#

Solution#

Method 1 – Dynamic Programming with Prefix Sums#

Intuition#

Approach#

Code#

Complexity#