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 th

numberOfStableArrays.js

/**
 * @param {number} zero
 * @param {number} one
 * @param {number} limit 
 * @return {number}
 */
var numberOfStableArrays = function (zero, one, limit) {
    const MOD = 1_000_000_007;

    // ------------------------------------------------------------
    // dp[a][b][c][d] means:
    //   a = number of 0s used so far
    //   b = number of 1s used so far
    //   c = last bit placed (0 or 1)
    //   d = length of the current run of c
    //
    // Example:
    //   dp[3][2][1][2] = number of arrays that used 3 zeros, 2 ones,
    //                    end with bit 1, and have a run of two 1s at the end.
    //
    // This DP ensures:
    //   - we never exceed the run limit
    //   - we count all valid sequences
    // ------------------------------------------------------------

    // Create the DP array filled with zeros
    const dp = Array.from({ length: zero + 1 }, () =>
        Array.from({ length: one + 1 }, () =>
            [
                Array(limit + 1).fill(0), // last bit = 0
                Array(limit + 1).fill(0)  // last bit = 1
            ]
        )
    );

    // ------------------------------------------------------------
    // Base cases:
    // We can start with either a single 0 or a single 1.
    // ------------------------------------------------------------
    if (zero > 0) dp[1][0][0][1] = 1; // start with "0"
    if (one > 0) dp[0][1][1][1] = 1; // start with "1"

    // ------------------------------------------------------------
    // Fill DP table
    // ------------------------------------------------------------
    for (let a = 0; a <= zero; a++) {
        for (let b = 0; b <= one; b++) {
            for (let last = 0; last <= 1; last++) {
                for (let run = 1; run <= limit; run++) {
                    const ways = dp[a][b][last][run];
                    if (ways === 0) continue; // no sequences here

                    // ------------------------------------------------
                    // OPTION 1: Append a 0
                    // ------------------------------------------------
                    if (a < zero) {
                        if (last === 0) {
                            // Continue a run of 0s — only allowed if run < limit
                            if (run < limit) {
                                dp[a + 1][b][0][run + 1] =
                                    (dp[a + 1][b][0][run + 1] + ways) % MOD;
                            }
                        } else {
                            // Switching from 1 → 0 resets run length to 1
                            dp[a + 1][b][0][1] =
                                (dp[a + 1][b][0][1] + ways) % MOD;
                        }
                    }

                    // ------------------------------------------------
                    // OPTION 2: Append a 1
                    // ------------------------------------------------
                    if (b < one) {
                        if (last === 1) {
                            // Continue a run of 1s — only allowed if run < limit
                            if (run < limit) {
                                dp[a][b + 1][1][run + 1] =
                                    (dp[a][b + 1][1][run + 1] + ways) % MOD;
                            }
                        } else {
                            // Switching from 0 → 1 resets run length to 1
                            dp[a][b + 1][1][1] =
                                (dp[a][b + 1][1][1] + ways) % MOD;
                        }
                    }
                }
            }
        }
    }

    // ------------------------------------------------------------
    // Final answer:
    // Sum all DP states that used exactly zero 0s and one 1s,
    // regardless of what the last bit was or how long the run is.
    // ------------------------------------------------------------
    let result = 0;
    for (let last = 0; last <= 1; last++) {
        for (let run = 1; run <= limit; run++) {
            result = (result + dp[zero][one][last][run]) % MOD;
        }
    }

    return result;
};