Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A stable array has no run of equal bits longer than limit. Trying every possible final run would introduce an extra factor of limit. Instead, build arrays one bit at a time and remove the newly overlong runs with a single subtraction.

Approach

Store dp[z][o][0] and dp[z][o][1], the numbers of valid arrays with those bit counts ending in zero or one. A pure run has one arrangement when its length is at most limit, and none otherwise; use these as boundary states.

To end in zero, append zero to either state at (z - 1, o). The invalid results have a suffix of exactly limit + 1 zeros created by that append. Removing this suffix leaves a valid prefix ending in one, counted by dp[z - limit - 1][o][1], which is subtracted when its index exists. Compute the symmetric transition for a final one.

Fill states in increasing bit counts and keep values modulo 1,000,000,007. Each transition uses a constant number of earlier states. Add the two final states to obtain the total.

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).