3129. Find All Possible Stable Binary Arrays I

/**
 * Problem: LeetCode 3129 - Find All Possible Stable Binary Arrays I
 * Difficulty: Medium
 * Language: Java
 * Author: CodeByTushu
 */
class Solution {
    public int numberOfStableArrays(int zero, int one, int limit) {
        final int MOD = 1_000_000_007;

        // dp0[i][j] = valid arrays with i zeros and j ones ending in 0
        // dp1[i][j] = valid arrays with i zeros and j ones ending in 1
        long[][] dp0 = new long[zero + 1][one + 1];
        long[][] dp1 = new long[zero + 1][one + 1];

        // Base cases: purely zeros or purely ones
        for (int i = 1; i <= Math.min(zero, limit); i++) {
            dp0[i][0] = 1;
        }
        for (int j = 1; j <= Math.min(one, limit); j++) {
            dp1[0][j] = 1;
        }

        // DP state transitions
        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                // Ending in 0: append '0' to any valid prefix (i-1, j)
                dp0[i][j] = (dp0[i - 1][j] + dp1[i - 1][j]) % MOD;
                if (i > limit) {
                    // Subtract invalid configurations exceeding 'limit' consecutive zeros
                    dp0[i][j] = (dp0[i][j] - dp1[i - 1 - limit][j] + MOD) % MOD;
                }

                // Ending in 1: append '1' to any valid prefix (i, j-1)
                dp1[i][j] = (dp0[i][j - 1] + dp1[i][j - 1]) % MOD;
                if (j > limit) {
                    // Subtract invalid configurations exceeding 'limit' consecutive ones
                    dp1[i][j] = (dp1[i][j] - dp0[i][j - 1 - limit] + MOD) % MOD;
                }
            }
        }

        return (int) ((dp0[zero][one] + dp1[zero][one]) % MOD);
    }
}

"""
Problem: LeetCode 3129 - Find All Possible Stable Binary Arrays I
Difficulty: Medium
Language: Python
Author: CodeByTushu
"""
class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 1_000_000_007

        # dp0[i][j] = valid stable arrays with i zeros and j ones ending with 0
        # dp1[i][j] = valid stable arrays with i zeros and j ones ending with 1
        dp0 = [[0] * (one + 1) for _ in range(zero + 1)]
        dp1 = [[0] * (one + 1) for _ in range(zero + 1)]

        # Base cases
        for i in range(1, min(zero, limit) + 1):
            dp0[i][0] = 1
        for j in range(1, min(one, limit) + 1):
            dp1[0][j] = 1

        # DP transitions
        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                dp0[i][j] = (dp0[i - 1][j] + dp1[i - 1][j]) % MOD
                if i > limit:
                    dp0[i][j] = (dp0[i][j] - dp1[i - 1 - limit][j] + MOD) % MOD

                dp1[i][j] = (dp0[i][j - 1] + dp1[i][j - 1]) % MOD
                if j > limit:
                    dp1[i][j] = (dp1[i][j] - dp0[i][j - 1 - limit] + MOD) % MOD

        return (dp0[zero][one] + dp1[zero][one]) % MOD

/**
 * Problem: LeetCode 3129 - Find All Possible Stable Binary Arrays I
 * Difficulty: Medium
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>

using namespace std;

class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        const int MOD = 1'000'000'007;

        // dp0[i][j]: valid stable arrays with i zeros and j ones ending in 0
        // dp1[i][j]: valid stable arrays with i zeros and j ones ending in 1
        vector<vector<int>> dp0(zero + 1, vector<int>(one + 1, 0));
        vector<vector<int>> dp1(zero + 1, vector<int>(one + 1, 0));

        // Base cases
        for (int i = 1; i <= min(zero, limit); i++) {
            dp0[i][0] = 1;
        }
        for (int j = 1; j <= min(one, limit); j++) {
            dp1[0][j] = 1;
        }

        // State transitions
        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                dp0[i][j] = (dp0[i - 1][j] + dp1[i - 1][j]) % MOD;
                if (i > limit) {
                    dp0[i][j] = (dp0[i][j] - dp1[i - 1 - limit][j] + MOD) % MOD;
                }

                dp1[i][j] = (dp0[i][j - 1] + dp1[i][j - 1]) % MOD;
                if (j > limit) {
                    dp1[i][j] = (dp1[i][j] - dp0[i][j - 1 - limit] + MOD) % MOD;
                }
            }
        }

        return (dp0[zero][one] + dp1[zero][one]) % MOD;
    }
};

/**
 * Problem: LeetCode 3129 - Find All Possible Stable Binary Arrays I
 * Difficulty: Medium
 * Language: JavaScript
 * Author: CodeByTushu
 */
/**
 * @param {number} zero
 * @param {number} one
 * @param {number} limit
 * @return {number}
 */
var numberOfStableArrays = function(zero, one, limit) {
    const MOD = 1000000007n;

    // dp0[i][j]: valid stable arrays with i zeros and j ones ending with 0
    // dp1[i][j]: valid stable arrays with i zeros and j ones ending with 1
    const dp0 = Array.from({ length: zero + 1 }, () => new BigInt64Array(one + 1));
    const dp1 = Array.from({ length: zero + 1 }, () => new BigInt64Array(one + 1));

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

    for (let i = 1; i <= zero; i++) {
        for (let j = 1; j <= one; j++) {
            dp0[i][j] = (dp0[i - 1][j] + dp1[i - 1][j]) % MOD;
            if (i > limit) {
                dp0[i][j] = (dp0[i][j] - dp1[i - 1 - limit][j] + MOD) % MOD;
            }

            dp1[i][j] = (dp0[i][j - 1] + dp1[i][j - 1]) % MOD;
            if (j > limit) {
                dp1[i][j] = (dp1[i][j] - dp0[i][j - 1 - limit] + MOD) % MOD;
            }
        }
    }

    return Number((dp0[zero][one] + dp1[zero][one]) % MOD);
};