👨‍💻 By Expert Funda 📅 Tuesday, March 10, 2026

LeetCode 3130 – Find All Possible Stable Binary Arrays II

LeetCode 3130 – Find All Possible Stable Binary Arrays II | Dynamic Programming

LeetCode 3130 – Find All Possible Stable Binary Arrays II

In this article, we will learn how to solve LeetCode 3130 – Find All Possible Stable Binary Arrays II using Dynamic Programming.

This is an advanced DP problem where we must carefully control how many consecutive elements appear in the array.

Problem Summary

We are given three integers:

  • zero → number of zeros
  • one → number of ones
  • limit → maximum allowed consecutive identical numbers

We must build binary arrays such that:

  • The array contains exactly zero zeros
  • The array contains exactly one ones
  • No more than limit consecutive identical numbers

Return the total number of valid arrays.

Example

Input: 
zero = 1
one = 2
limit = 1
Possible permutations: 
011
101
110
Validation: 
011 → invalid (two consecutive ones)
101 → valid
110 → invalid
Answer: 
1

Key Observation

The difficulty of this problem is controlling consecutive identical numbers.

For example if limit = 2:

00   allowed
11   allowed
000  not allowed
111  not allowed

So while constructing the array we must remember:

  • how many zeros we used
  • how many ones we used
  • what the last element was
This leads to a Dynamic Programming solution.

DP State Definition

dp[i][j][lastBit]
Where:
Variable Meaning
i zeros used
j ones used
lastBit last number placed (0 or 1)
Example: 
dp[2][1][0]
means:
  • 2 zeros used
  • 1 one used
  • array ends with 0

DP Transition

Case 1 – Array ends with 0

To place a zero we come from: 
dp[i-1][j][0]
dp[i-1][j][1]
So: 
dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1]
But this might create sequences like: 
000
which exceed the limit. So we subtract invalid cases: 
dp[i-limit-1][j][1]

Case 2 – Array ends with 1

Similarly: 
dp[i][j][1] = dp[i][j-1][0] + dp[i][j-1][1]
And remove invalid sequences: 
dp[i][j-limit-1][0]
This trick avoids tracking consecutive counts directly.

Java Implementation

class Solution {

    public int numberOfStableArrays(int zero, int one, int limit) {

        final int MOD = 1000000007;
        int[][][] dp = new int[zero + 1][one + 1][2];

        for (int i = 0; i <= zero; i++) {
            for (int j = 0; j <= one; j++) {

                for (int lastBit = 0; lastBit <= 1; lastBit++) {

                    if (i == 0) {

                        if (lastBit == 0 || j > limit)
                            dp[i][j][lastBit] = 0;
                        else
                            dp[i][j][lastBit] = 1;

                    } else if (j == 0) {

                        if (lastBit == 1 || i > limit)
                            dp[i][j][lastBit] = 0;
                        else
                            dp[i][j][lastBit] = 1;

                    } else if (lastBit == 0) {

                        dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];

                        if (i > limit)
                            dp[i][j][0] -= dp[i - limit - 1][j][1];

                    } else {

                        dp[i][j][1] = dp[i][j - 1][0] + dp[i][j - 1][1];

                        if (j > limit)
                            dp[i][j][1] -= dp[i][j - limit - 1][0];
                    }

                    dp[i][j][lastBit] %= MOD;

                    if (dp[i][j][lastBit] < 0)
                        dp[i][j][lastBit] += MOD;
                }
            }
        }

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

Time Complexity

O(zero × one)

Space Complexity

O(zero × one)

Video Explanation

You can watch the complete explanation here:

Key Takeaways

  • This problem uses Dynamic Programming.
  • We track how many zeros and ones are used.
  • We track the last element placed.
  • Prefix subtraction removes invalid sequences efficiently.

Follow ExpertFunda for more DSA tutorials, system design concepts, and coding interview preparation.

Continue Reading →