👨‍💻 By Expert Funda 📅 Monday, March 9, 2026

LeetCode 3129 – Find All Possible Stable Binary Arrays I

LeetCode 3129 – Find All Possible Stable Binary Arrays I | Dynamic Programming

LeetCode 3129 – Find All Possible Stable Binary Arrays I

In this tutorial we will solve LeetCode 3129 – Find All Possible Stable Binary Arrays I. This is a very interesting Dynamic Programming problem where we need to count valid binary arrays under a constraint on consecutive elements.

Problem Statement

We are given three integers:

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

We must count the number of binary arrays that:

  • Use exactly zero number of 0s
  • Use exactly one number of 1s
  • Contain no more than limit consecutive identical numbers
These arrays are called Stable Binary Arrays.

Example

Input 
zero = 2
one = 1
limit = 2
Possible Arrays 
001
010
100
All arrays satisfy the rule that no more than 2 identical numbers appear consecutively. Output 
3

Key Idea

Instead of building arrays directly, we use Dynamic Programming. We define two DP tables: 
dp0[i][j] → arrays using i zeros and j ones ending with 0
dp1[i][j] → arrays using i zeros and j ones ending with 1
Why do we separate them? Because the limit constraint depends on the last element placed.

Base Cases

If we only place zeros: 
0
00
000
These are valid only if: 
zeros ≤ limit
So we initialize: 
dp0[i][0] = 1
Similarly for ones: 
dp1[0][j] = 1

DP Transition

Case 1 – Array ending with 0

To end with 0, the previous element must be 1. We append a block of zeros: 
...1 + 0
...1 + 00
...1 + 000
But block size cannot exceed limit. Therefore: 
dp0[i][j] += dp1[i-k][j]
for 1 ≤ k ≤ limit

Case 2 – Array ending with 1

Similarly: 
...0 + 1
...0 + 11
...0 + 111
So: 
dp1[i][j] += dp0[i][j-k]

Java Solution

class Solution {

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

        int MOD = 1_000_000_007;

        long[][] dp0 = new long[zero + 1][one + 1];
        long[][] dp1 = new long[zero + 1][one + 1];

        for (int i = 1; i <= zero && i <= limit; i++)
            dp0[i][0] = 1;

        for (int j = 1; j <= one && j <= limit; j++)
            dp1[0][j] = 1;

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

                long sum0 = 0;

                for (int k = 1; k <= limit && k <= i; k++)
                    sum0 = (sum0 + dp1[i-k][j]) % MOD;

                dp0[i][j] = sum0;

                long sum1 = 0;

                for (int k = 1; k <= limit && k <= j; k++)
                    sum1 = (sum1 + dp0[i][j-k]) % MOD;

                dp1[i][j] = sum1;
            }
        }

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

Complexity Analysis

Type Complexity
Time Complexity O(zero × one × limit)
Space Complexity O(zero × one)

Why This Solution Works

The key insight is that instead of tracking consecutive elements explicitly, we treat consecutive numbers as blocks of size 1 to limit.

This removes an entire dimension from the DP state and allows the problem to be solved efficiently.

Watch Full Video Explanation

Watch the complete explanation on YouTube:

Conclusion

In this problem we learned how to transform a recursive idea into an efficient dynamic programming solution.

  • Start with recursion
  • Understand the state transitions
  • Optimize using DP tables

This pattern appears frequently in coding interviews and competitive programming.

Follow ExpertFunda for more DSA tutorials and coding interview preparation.

Continue Reading →