Skip to content

3129. Find All Possible Stable Binary Arrays I

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], 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

Solutions

Thinking

A stable array never has more than \(limit\) equal bits in a row. Backtracking over \(zero\) zeros and \(one\) ones explodes.

Validity after a prefix depends only on remaining zeros and ones and on which bit is written next. Overflow is the case of writing \(limit+1\) equal bits after the opposite bit.

Let \(dfs(i,j,k)\) be the number of ways with \(i\) zeros and \(j\) ones left and next bit \(k\). Add the same-color and other-color transitions and subtract the overflow term. Memoization yields \(O(zero\cdot one)\) states.

We define a function \(\textit{dfs}(i, j, k)\) to represent the number of stable binary arrays that satisfy the problem conditions when there are \(i\) zeros and \(j\) ones remaining to place, and the next digit to fill is \(k\). Then the answer is \(\textit{dfs}(\textit{zero}, \textit{one}, 0) + \textit{dfs}(\textit{zero}, \textit{one}, 1)\).

The computation process of \(\textit{dfs}(i, j, k)\) is as follows:

  • If \(i \lt 0\) or \(j \lt 0\), return \(0\).
  • If \(i = 0\), then return \(1\) when \(k = 1\) and \(j \leq \textit{limit}\); otherwise return \(0\).
  • If \(j = 0\), then return \(1\) when \(k = 0\) and \(i \leq \textit{limit}\); otherwise return \(0\).
  • If \(k = 0\), we consider the case where the previous digit is \(0\), i.e., \(\textit{dfs}(i - 1, j, 0)\), and the case where the previous digit is \(1\), i.e., \(\textit{dfs}(i - 1, j, 1)\). If the previous digit is \(0\), there may be more than \(\textit{limit}\) zeros in a subarray, which means the case where the \((\textit{limit} + 1)\)-th digit from the end is \(1\) is invalid, so we subtract this case: \(\textit{dfs}(i - \textit{limit} - 1, j, 1)\).
  • If \(k = 1\), we consider the case where the previous digit is \(0\), i.e., \(\textit{dfs}(i, j - 1, 0)\), and the case where the previous digit is \(1\), i.e., \(\textit{dfs}(i, j - 1, 1)\). If the previous digit is \(1\), there may be more than \(\textit{limit}\) ones in a subarray, which means the case where the \((\textit{limit} + 1)\)-th digit from the end is \(0\) is invalid, so we subtract this case: \(\textit{dfs}(i, j - \textit{limit} - 1, 0)\).

To avoid repeated computation, we use memoized search.

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

 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
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
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 }, () => [-1, -1]),
    );

    const dfs = (i: number, j: number, k: number): number => {
        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;
        }
        let 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 (f[i][j][k] = 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

The recurrence has no aftereffect; recursion still pays cache and call overhead near the upper limits.

The same transition fills a table \(f[i][j][k]\): \(i\) zeros and \(j\) ones used, last bit \(k\).

Base cases are monochrome strings no longer than \(limit\). After iterating with a modulus, read \(f[zero][one][0]+f[zero][one][1]\).

We can also convert the memoized search in Solution 1 into dynamic programming.

We define \(f[i][j][k]\) as the number of stable binary arrays that use \(i\) zeros and \(j\) ones, with the last digit being \(k\). Then 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 equations are 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(\textit{zero} \times \textit{one})\), and the space complexity is \(O(\textit{zero} \times \textit{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