Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The stability condition is equivalent to forbidding runs longer than limit. Count arrays by how many zeros and ones they contain and by their last bit. Appending a bit counts almost all desired arrays; subtract the precise cases where it creates a run of limit + 1.

Approach

Let dp[z][o][b] count valid arrays with z zeros, o ones, and final bit b. Initialize all-zero and all-one arrays to one only when their lengths do not exceed limit.

For mixed arrays ending in zero, add both states with z - 1 zeros and o ones. If z > limit, subtract dp[z - limit - 1][o][1]: appending limit + 1 zeros to each of those prefixes describes exactly the newly invalid arrays. Apply the symmetric recurrence for arrays ending in one.

Compute the table in increasing counts, reducing modulo 1,000,000,007 and normalizing subtractions. The two final-bit categories are disjoint, so their sum at the requested counts is the answer.

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 10**9 + 7
        dp = [[[0] * 2 for _ in range(one + 1)] for _ in range(zero + 1)]

        for z in range(1, min(limit, zero) + 1):
            dp[z][0][0] = 1

        for o in range(1, min(limit, one) + 1):
            dp[0][o][1] = 1

        for z in range(1, zero + 1):
            for o in range(1, one + 1):
                dp[z][o][0] = (dp[z - 1][o][0] + dp[z - 1][o][1]) % MOD
                if z > limit:
                    dp[z][o][0] = (dp[z][o][0] - dp[z - limit - 1][o][1]) % MOD
                dp[z][o][1] = (dp[z][o - 1][0] + dp[z][o - 1][1]) % MOD
                if o > limit:
                    dp[z][o][1] = (dp[z][o][1] - dp[z][o - limit - 1][0]) % MOD

        return (dp[zero][one][0] + dp[zero][one][1]) % MOD

Complexity analysis

Let z = zero and o = one. Time: O(z * o). Auxiliary space: O(z * o).