Find All Possible Stable Binary Arrays I

Medium
Watch on YouTube ↗

Solution

class Solution {
    int mod = 1_000_000_007;
    int dp[][][][];
    public int numberOfStableArrays(int zeros, int ones, int limit) {
        dp = new int[2][zeros+1][ones+1][limit+1];
        for(int[][][] a : dp) {
            for(int[][] b : a) {
                for(int[] c : b) {
                    Arrays.fill(c, -1);
                }
            }
        }
        return (helper(zeros-1, ones, 0, 1, limit) + helper(zeros, ones-1, 1
        , 1 , limit))%mod;
    }

    int helper(int zeros, int ones, int lastbit, int streak, int limit) {
        // base condition
        if(streak > limit)
            return 0; // invalid
        if(zeros==0 && ones==0)
            return 1;
        if(dp[lastbit][zeros][ones][streak]!=-1)
            return dp[lastbit][zeros][ones][streak];
        int ways = 0;
        if(lastbit ==0 ) {
            if(zeros > 0)
                ways = (ways + helper(zeros-1, ones, 0, streak + 1, limit))%mod;
            if(ones > 0)
                ways = (ways + helper(zeros, ones-1, 1, 1, limit))%mod;
        }
        else {
            if(zeros > 0)
                ways = (ways + helper(zeros-1, ones, 0, 1, limit))%mod;
            if(ones > 0)
                ways = (ways + helper(zeros, ones-1, 1, streak+1, limit))%mod;
        }

        return dp[lastbit][zeros][ones][streak] = ways;
    }
}