LeetCode 3129 - Find All Possible Stable Binary Arrays I

In this problem, we need to count how many binary arrays can be formed using exactly zero copies of 0 and exactly one copies of 1, while satisfying an additional stability condition.

leetcodemediumdynamic-programmingprefix-sum

LeetCode Problem 3129

Difficulty: 🟡 Medium
Topics: Dynamic Programming, Prefix Sum

Solution

Problem Understanding

In this problem, we need to count how many binary arrays can be formed using exactly zero copies of 0 and exactly one copies of 1, while satisfying an additional stability condition.

A binary array is considered stable if every subarray whose length is greater than limit contains both 0 and 1. Another way to interpret this condition is that we are not allowed to have more than limit consecutive identical values anywhere in the array.

For example, if limit = 2, then sequences like [0,0,0] or [1,1,1] are forbidden because they contain three consecutive equal elements. However, [0,0,1,1] is valid because no run exceeds length 2.

The input consists of three integers:

  • zero, the exact number of zeros we must place
  • one, the exact number of ones we must place
  • limit, the maximum allowed length of any consecutive run of equal values

The output is the total number of valid arrays satisfying all conditions, modulo 10^9 + 7.

The constraints are:

  • 1 <= zero, one, limit <= 200

These constraints are extremely important. Since both counts can reach 200, the total array length can be as large as 400. A brute-force generation of all binary arrays is completely infeasible because the number of possible arrangements grows exponentially.

The problem strongly suggests a dynamic programming solution because:

  • We build arrays incrementally
  • The validity of future choices depends on the recent sequence
  • Many subproblems overlap

Several edge cases are especially important:

  • When limit = 1, the array must strictly alternate between 0 and 1
  • When either count is much larger than the other, it may become impossible to avoid long runs
  • When limit is larger than both counts, almost every arrangement becomes valid
  • Arrays ending with 0 and arrays ending with 1 must be handled separately because future transitions differ

Approaches

Brute Force

A straightforward brute-force solution would generate every possible binary array containing exactly zero zeros and one ones. For each generated array, we would scan all consecutive runs and verify that no run exceeds limit.

This approach is correct because it explicitly checks every possible arrangement and filters out invalid ones.

However, it is far too slow. The number of binary arrays with zero + one positions is:

$$\binom{zero + one}{zero}$$

In the worst case, this becomes enormous. For example, with zero = 200 and one = 200, the number of combinations is astronomically large.

Therefore, brute force is not practical.

Optimal Dynamic Programming

The key observation is that the validity of the array depends only on:

  • How many zeros have been used
  • How many ones have been used
  • What the last placed digit was
  • How long the current consecutive run is

Instead of constructing every full array independently, we reuse results from overlapping subproblems.

We define DP states based on the remaining counts and the ending value. The transition works by appending either 0 or 1, while ensuring the consecutive run length never exceeds limit.

A particularly elegant optimization uses prefix-style recurrence relations:

  • dp0[i][j] = number of valid arrays using i zeros and j ones that end in 0
  • dp1[i][j] = number of valid arrays using i zeros and j ones that end in 1

We transition by appending blocks of zeros or ones with size at most limit.

This avoids explicitly storing run lengths in the DP state, reducing complexity significantly.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(zero + one) Generates all binary arrays
Optimal O(zero × one) O(zero × one) Dynamic programming with optimized transitions

Algorithm Walkthrough

  1. Define two DP tables.

We create:

  • dp0[i][j], the number of stable arrays using i zeros and j ones that end with 0
  • dp1[i][j], the number of stable arrays using i zeros and j ones that end with 1

Separating by ending digit is important because the next transition depends on what the current run value is. 2. Initialize base cases.

Arrays containing only zeros are valid only if the count does not exceed limit.

Therefore:

  • dp0[i][0] = 1 for 1 <= i <= limit
  • dp1[0][j] = 1 for 1 <= j <= limit

These represent arrays like:

  • [0]
  • [0,0]
  • [1]
  • [1,1]
  1. Build transitions for arrays ending in 0.

To construct an array ending in 0, we append a block of k zeros to a valid array ending in 1.

The block size must satisfy:

$$1 \le k \le limit$$

So:

$$dp0[i][j] += dp1[i-k][j]$$

for every valid k. 4. Build transitions for arrays ending in 1.

Similarly:

$$dp1[i][j] += dp0[i][j-k]$$

for every valid k. 5. Apply modulo operations.

Since the answer can become extremely large, every addition is performed modulo:

$$10^9 + 7$$ 6. Compute the final answer.

The final stable arrays may end with either 0 or 1, so the answer is:

$$dp0[zero][one] + dp1[zero][one]$$

Why it works

The DP works because every stable binary array can be uniquely decomposed into alternating blocks of zeros and ones, where each block length is at most limit.

The transitions enumerate all valid possibilities for the final block while ensuring the previous portion of the array is already stable. Since every valid array has exactly one final block configuration, each array is counted exactly once.

Python Solution

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 10**9 + 7

        dp0 = [[0] * (one + 1) for _ in range(zero + 1)]
        dp1 = [[0] * (one + 1) for _ in range(zero + 1)]

        # Base cases for arrays containing only zeros
        for i in range(1, min(zero, limit) + 1):
            dp0[i][0] = 1

        # Base cases for arrays containing only ones
        for j in range(1, min(one, limit) + 1):
            dp1[0][j] = 1

        for i in range(zero + 1):
            for j in range(one + 1):

                # Build arrays ending with 0
                for k in range(1, min(i, limit) + 1):
                    if i == k and j == 0:
                        continue
                    dp0[i][j] += dp1[i - k][j]
                    dp0[i][j] %= MOD

                # Build arrays ending with 1
                for k in range(1, min(j, limit) + 1):
                    if j == k and i == 0:
                        continue
                    dp1[i][j] += dp0[i][j - k]
                    dp1[i][j] %= MOD

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

The implementation directly follows the DP formulation described earlier.

The two tables dp0 and dp1 separately track arrays ending in different digits. This separation is necessary because extending an array depends on the value of its current suffix.

The initialization handles arrays made entirely of one digit. These arrays are valid only if their length does not exceed limit.

The nested loops iterate over every possible count of used zeros and ones. For each state, we try appending a valid block of zeros or ones.

The inner loops over k represent the size of the final consecutive block being appended. Restricting k <= limit guarantees the stability condition is preserved.

Finally, the answer combines both ending possibilities.

Go Solution

func numberOfStableArrays(zero int, one int, limit int) int {
	const MOD int = 1e9 + 7

	dp0 := make([][]int, zero+1)
	dp1 := make([][]int, zero+1)

	for i := 0; i <= zero; i++ {
		dp0[i] = make([]int, one+1)
		dp1[i] = make([]int, one+1)
	}

	// Base cases for only zeros
	for i := 1; i <= min(zero, limit); i++ {
		dp0[i][0] = 1
	}

	// Base cases for only ones
	for j := 1; j <= min(one, limit); j++ {
		dp1[0][j] = 1
	}

	for i := 0; i <= zero; i++ {
		for j := 0; j <= one; j++ {

			// Arrays ending with 0
			for k := 1; k <= min(i, limit); k++ {
				if i == k && j == 0 {
					continue
				}

				dp0[i][j] += dp1[i-k][j]
				dp0[i][j] %= MOD
			}

			// Arrays ending with 1
			for k := 1; k <= min(j, limit); k++ {
				if j == k && i == 0 {
					continue
				}

				dp1[i][j] += dp0[i][j-k]
				dp1[i][j] %= MOD
			}
		}
	}

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

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go implementation mirrors the Python logic closely.

Since Go does not provide built-in dynamic multidimensional arrays, we explicitly allocate the 2D slices using make.

Modulo operations are applied after every update to avoid integer overflow. Go integers are large enough for intermediate arithmetic here, but modulo reduction is still necessary for correctness.

The helper min function is included because Go does not provide one for integers in the standard library.

Worked Examples

Example 1

Input:

zero = 1
one = 1
limit = 2

We initialize:

State Value
dp0[1][0] 1
dp1[0][1] 1

Now compute transitions.

For dp0[1][1]:

  • Append one 0 to arrays ending in 1
  • dp1[0][1] = 1

So:

State Calculation Result
dp0[1][1] dp1[0][1] 1

For dp1[1][1]:

  • Append one 1 to arrays ending in 0
  • dp0[1][0] = 1
State Calculation Result
dp1[1][1] dp0[1][0] 1

Final answer:

$$1 + 1 = 2$$

Valid arrays:

[0,1]
[1,0]

Example 2

Input:

zero = 1
one = 2
limit = 1

Since limit = 1, no consecutive equal digits are allowed.

Possible arrays:

[1,0,1]   valid
[1,1,0]   invalid
[0,1,1]   invalid

DP transitions only allow blocks of size 1.

Final answer:

$$1$$

Example 3

Input:

zero = 3
one = 3
limit = 2

Now blocks of length 1 or 2 are allowed.

The DP gradually builds all valid configurations while excluding:

000
111

as consecutive runs.

The final computed value becomes:

$$14$$

which matches the problem statement.

Complexity Analysis

Measure Complexity Explanation
Time O(zero × one × limit) Each DP state tries up to limit transitions
Space O(zero × one) Two DP tables are stored

The DP contains (zero + 1) × (one + 1) states. For each state, we iterate over at most limit possible block sizes for zeros and ones. Therefore, the total time complexity is:

$$O(zero \times one \times limit)$$

Given the constraints are at most 200, this is easily fast enough.

The space complexity comes from storing the two DP tables.

Test Cases

sol = Solution()

assert sol.numberOfStableArrays(1, 1, 2) == 2
# Basic smallest mixed case

assert sol.numberOfStableArrays(1, 2, 1) == 1
# Alternation required

assert sol.numberOfStableArrays(3, 3, 2) == 14
# Provided example

assert sol.numberOfStableArrays(2, 2, 1) == 2
# Only alternating patterns valid

assert sol.numberOfStableArrays(2, 1, 2) == 3
# All permutations valid because limit is large enough

assert sol.numberOfStableArrays(3, 1, 1) == 0
# Impossible to avoid consecutive zeros

assert sol.numberOfStableArrays(1, 3, 1) == 0
# Impossible to avoid consecutive ones

assert sol.numberOfStableArrays(4, 4, 4) == 70
# No practical restriction on runs

assert sol.numberOfStableArrays(2, 3, 2) == 7
# Mixed counts with moderate limit

assert sol.numberOfStableArrays(5, 1, 2) == 0
# Too many zeros for the limit
Test Why
(1,1,2) Smallest nontrivial valid case
(1,2,1) Strict alternation
(3,3,2) Larger balanced example
(2,2,1) Consecutive duplicates forbidden
(2,1,2) Large enough limit allows all permutations
(3,1,1) Impossible due to excessive zeros
(1,3,1) Impossible due to excessive ones
(4,4,4) Constraint effectively inactive
(2,3,2) Moderate mixed configuration
(5,1,2) Run-length restriction blocks all arrays

Edge Cases

One important edge case occurs when limit = 1. In this situation, consecutive equal elements are completely forbidden. The array must strictly alternate between 0 and 1. Many implementations accidentally allow runs of length two because of off-by-one errors in the transition logic. This implementation prevents that by only allowing block sizes up to limit.

Another important case occurs when one count is much larger than the other. For example:

zero = 5
one = 1
limit = 2

There are not enough ones available to separate the zeros into valid groups. A naive implementation may incorrectly count invalid arrangements containing 000. The DP correctly avoids such states because no transition allows a block larger than limit.

A third critical edge case happens when the limit is very large relative to the counts. For example:

zero = 4
one = 4
limit = 10

In this scenario, every arrangement is valid because no possible run can exceed the limit. The algorithm still works correctly because the transition loops naturally allow all feasible block sizes without special handling.

Finally, arrays consisting entirely of one digit require careful initialization. Cases like:

zero = 3
one = 0

are valid only if 3 <= limit. The base-case initialization explicitly handles these scenarios so that the DP starts from correct states.