Skip to content

3130. Find All Possible Stable Binary Arrays II

Description

You are given 3 positive integers num_zeros, num_ones, and limit.

A binary array arr is called stable if:

  • The number of occurrences of 0 in arr is exactly num_zeros.
  • The number of occurrences of 1 in arr is exactly num_ones.
  • Each subarray of arr with a size greater than limit must contain at least one occurrence of both 0 and 1.

Return an integer denoting 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

Solutions

Thinking

The definition matches part I, but \(zero\) and \(one\) are larger, so backtracking is impossible. Stability still depends only on remaining counts and the next bit.

Overflow is again subtracted as the branch that writes \(limit+1\) equal bits. The state space stays \(O(zero\cdot one)\).

Reuse memoized \(dfs(i,j,k)\), reduce modulo \(10^9+7\), and clear the cache before returning.

We design a function \(dfs(i, j, k)\) to represent the number of stable binary arrays that satisfy the problem conditions when there are \(i\) \(0\)s and \(j\) \(1\)s left, and the next number to be filled is \(k\). The answer is \(dfs(zero, one, 0) + dfs(zero, one, 1)\).

The calculation process of the function \(dfs(i, j, k)\) is as follows:

  • If \(i < 0\) or \(j < 0\), return \(0\).
  • If \(i = 0\), return \(1\) when \(k = 1\) and \(j \leq \textit{limit}\), otherwise return \(0\).
  • If \(j = 0\), return \(1\) when \(k = 0\) and \(i \leq \textit{limit}\), otherwise return \(0\).
  • If \(k = 0\), we consider the case where the previous number is \(0\), \(dfs(i - 1, j, 0)\), and the case where the previous number is \(1\), \(dfs(i - 1, j, 1)\). If the previous number is \(0\), it may cause more than \(\textit{limit}\) \(0\)s in the subarray, i.e., the situation where the \(\textit{limit} + 1\)
 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:
    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

 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
class Solution {
    private final int mod = (int) 1e9 + 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];
    }
}

 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
class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        const int mod = 1e9 + 7;
        using ll = long long;
        vector<vector<array<ll, 2>>> f = vector<vector<array<ll, 2>>>(zero + 1, vector<array<ll, 2>>(one + 1, {-1, -1}));
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> ll {
            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;
        };
        return (dfs(zero, one, 0) + dfs(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
35
36
37
38
39
func numberOfStableArrays(zero int, one int, limit int) int {
    const mod int = 1e9 + 7
    f := make([][][2]int, zero+1)
    for i := range f {
        f[i] = make([][2]int, one+1)
        for j := range f[i] {
            f[i][j] = [2]int{-1, -1}
        }
    }
    var dfs func(i, j, k int) int
    dfs = func(i, j, k int) int {
        if i < 0 || j < 0 {
            return 0
        }
        if i == 0 {
            if k == 1 && j <= limit {
                return 1
            }
            return 0
        }
        if j == 0 {
            if k == 0 && i <= limit {
                return 1
            }
            return 0
        }
        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
    }
    return (dfs(zero, one, 0) + dfs(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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
impl Solution {
    pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;

        fn dfs(
            i: i32,
            j: i32,
            k: usize,
            limit: i32,
            f: &mut Vec<Vec<[i64; 2]>>,
        ) -> i64 {
            if i < 0 || j < 0 {
                return 0;
            }

            if i == 0 {
                return if k == 1 && j <= limit { 1 } else { 0 };
            }

            if j == 0 {
                return if k == 0 && i <= limit { 1 } else { 0 };
            }

            let (iu, ju) = (i as usize, j as usize);

            if f[iu][ju][k] != -1 {
                return f[iu][ju][k];
            }

            let res = if k == 0 {
                (
                    dfs(i - 1, j, 0, limit, f)
                    + dfs(i - 1, j, 1, limit, f)
                    - dfs(i - limit - 1, j, 1, limit, f)
                    + MOD
                ) % MOD
            } else {
                (
                    dfs(i, j - 1, 0, limit, f)
                    + dfs(i, j - 1, 1, limit, f)
                    - dfs(i, j - limit - 1, 0, limit, f)
                    + MOD
                ) % MOD
            };

            f[iu][ju][k] = res;
            res
        }

        let mut f = vec![vec![[-1_i64; 2]; (one + 1) as usize]; (zero + 1) as usize];

        ((dfs(zero, one, 0, limit, &mut f) + dfs(zero, one, 1, limit, &mut f)) % MOD) as i32
    }
}

Solution 2: Dynamic Programming

Thinking

Memoization is already polynomial, yet recursion and cache overhead grow with the larger limits.

Fill \(f[i][j][k]\) iteratively in increasing \(i\) and \(j\), with the same base cases as part I.

Apply the modulus in the recurrence and return \(f[zero][one][0]+f[zero][one][1]\) without a call stack.

We can also convert the memoization search of Solution 1 into dynamic programming.

We define \(f[i][j][k]\) as the number of stable binary arrays using \(i\) \(0\)s and \(j\) \(1\)s, and the last number is \(k\). So the answer is \(f[zero][one][0] + f[zero][one][1]\).

Initially, we have \(f[i][0][0] = 1\), where \(1 \leq i \leq \min(\textit{limit}, \textit{zero})\); and \(f[0][j][1] = 1\), where \(1 \leq j \leq \min(\textit{limit}, \textit{one})\).

The state transition equation is as follows:

  • \(f[i][j][0] = f[i - 1][j][0] + f[i - 1][j][1] - f[i - \textit{limit} - 1][j][1]\).
  • \(f[i][j][1] = f[i][j - 1][0] + f[i][j - 1][1] - f[i][j - \textit{limit} - 1][0]\).

The time complexity is \(O(zero \times one)\), and the space complexity is \(O(zero \times one)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        mod = 10**9 + 7
        f = [[[0, 0] for _ in range(one + 1)] for _ in range(zero + 1)]
        for i in range(1, min(limit, zero) + 1):
            f[i][0][0] = 1
        for j in range(1, min(limit, one) + 1):
            f[0][j][1] = 1
        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                x = 0 if i - limit - 1 < 0 else f[i - limit - 1][j][1]
                y = 0 if j - limit - 1 < 0 else f[i][j - limit - 1][0]
                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x) % mod
                f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y) % mod
        return sum(f[zero][one]) % mod

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int numberOfStableArrays(int zero, int one, int limit) {
        final int mod = (int) 1e9 + 7;
        long[][][] f = new long[zero + 1][one + 1][2];
        for (int i = 1; i <= Math.min(zero, limit); ++i) {
            f[i][0][0] = 1;
        }
        for (int j = 1; j <= Math.min(one, limit); ++j) {
            f[0][j][1] = 1;
        }
        for (int i = 1; i <= zero; ++i) {
            for (int j = 1; j <= one; ++j) {
                long x = i - limit - 1 < 0 ? 0 : f[i - limit - 1][j][1];
                long y = j - limit - 1 < 0 ? 0 : f[i][j - limit - 1][0];
                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod) % mod;
                f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod) % mod;
            }
        }
        return (int) ((f[zero][one][0] + f[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
class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        const int mod = 1e9 + 7;
        using ll = long long;
        ll f[zero + 1][one + 1][2];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= min(zero, limit); ++i) {
            f[i][0][0] = 1;
        }
        for (int j = 1; j <= min(one, limit); ++j) {
            f[0][j][1] = 1;
        }
        for (int i = 1; i <= zero; ++i) {
            for (int j = 1; j <= one; ++j) {
                ll x = i - limit - 1 < 0 ? 0 : f[i - limit - 1][j][1];
                ll y = j - limit - 1 < 0 ? 0 : f[i][j - limit - 1][0];
                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod) % mod;
                f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod) % mod;
            }
        }
        return (f[zero][one][0] + f[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
func numberOfStableArrays(zero int, one int, limit int) int {
    const mod int = 1e9 + 7
    f := make([][][2]int, zero+1)
    for i := range f {
        f[i] = make([][2]int, one+1)
    }
    for i := 1; i <= min(zero, limit); i++ {
        f[i][0][0] = 1
    }
    for j := 1; j <= min(one, limit); j++ {
        f[0][j][1] = 1
    }
    for i := 1; i <= zero; i++ {
        for j := 1; j <= one; j++ {
            f[i][j][0] = (f[i-1][j][0] + f[i-1][j][1]) % mod
            if i-limit-1 >= 0 {
                f[i][j][0] = (f[i][j][0] - f[i-limit-1][j][1] + mod) % mod
            }
            f[i][j][1] = (f[i][j-1][0] + f[i][j-1][1]) % mod
            if j-limit-1 >= 0 {
                f[i][j][1] = (f[i][j][1] - f[i][j-limit-1][0] + mod) % mod
            }
        }
    }
    return (f[zero][one][0] + f[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
function numberOfStableArrays(zero: number, one: number, limit: number): number {
    const mod = 1e9 + 7;
    const f: number[][][] = Array.from({ length: zero + 1 }, () =>
        Array.from({ length: one + 1 }, () => [0, 0]),
    );

    for (let i = 1; i <= Math.min(limit, zero); i++) {
        f[i][0][0] = 1;
    }
    for (let j = 1; j <= Math.min(limit, one); j++) {
        f[0][j][1] = 1;
    }

    for (let i = 1; i <= zero; i++) {
        for (let j = 1; j <= one; j++) {
            const x = i - limit - 1 < 0 ? 0 : f[i - limit - 1][j][1];
            const y = j - limit - 1 < 0 ? 0 : f[i][j - limit - 1][0];
            f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod) % mod;
            f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod) % mod;
        }
    }

    return (f[zero][one][0] + f[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
impl Solution {
    pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
        let mod_: i64 = 1_000_000_007;

        let zero = zero as usize;
        let one = one as usize;
        let limit = limit as usize;

        let mut f = vec![vec![[0_i64; 2]; one + 1]; zero + 1];

        for i in 1..=zero.min(limit) {
            f[i][0][0] = 1;
        }

        for j in 1..=one.min(limit) {
            f[0][j][1] = 1;
        }

        for i in 1..=zero {
            for j in 1..=one {
                let x = if i > limit { f[i - limit - 1][j][1] } else { 0 };
                let y = if j > limit { f[i][j - limit - 1][0] } else { 0 };

                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod_) % mod_;
                f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod_) % mod_;
            }
        }

        ((f[zero][one][0] + f[zero][one][1]) % mod_) as i32
    }
}

Comments