3130. Find All Possible Stable Binary Arrays II

Problem Link

Description

---

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

Solution

---

Python3

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 10 ** 9 + 7
 
        # dp[zeroes][ones][last]
        dp = [[[0, 0] for _ in range(one + 1)] for _ in range(zero + 1)]
        
        for i in range(min(zero, limit) + 1):
            dp[i][0][0] = 1
        
        for j in range(min(one, limit) + 1):
            dp[0][j][1] = 1
        
        # dp[i][j][0] = dp[i - 1][j]
        # dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1[j][1]
        # same goes for dp[i][j][1] = dp[i][j - 1][0] + dp[i][j - 1][1]
        # for dp[i][j] we want to substract dp[i - limit - 1][j]
        # however, in dp[i - 1][j], it already substracts dp[i - limit - 2][j]
        # therefore, the count that need to be substracted is only dp[i - limit - 1][j] - dp[i - limit - 2][j]
        # since dp[i - limit - 2][j] == dp[i - limit - 1][j][0],
        # ans = dp[i - limit - 1][j] - dp[i - limit - 1][j][0]
        # ans = dp[i - limit - 1][j][1]
 
        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                dp[i][j][0] = sum(dp[i - 1][j])
                dp[i][j][1] = sum(dp[i][j - 1])
 
                if i > limit:
                    dp[i][j][0] -= dp[i - limit - 1][j][1]
                
                if j > limit:
                    dp[i][j][1] -= dp[i][j - limit - 1][0]
                
                for t in range(2):
                    dp[i][j][t] %= MOD
 
        return sum(dp[-1][-1]) % MOD