LeetCode Problem 3130

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Prefix Sum

Solution

LeetCode 3130 - Find All Possible Stable Binary Arrays II

Problem Understanding

The problem gives us three integers:

• zero, the exact number of 0s that must appear in the array
• one, the exact number of 1s that must appear in the array
• limit, the maximum allowed length of any consecutive block of identical values

We must count how many binary arrays satisfy all of the following:

1. The array contains exactly zero occurrences of 0
2. The array contains exactly one occurrences of 1
3. No subarray longer than limit consists entirely of the same value

The third condition is the most important part to interpret correctly. It means we cannot have more than limit consecutive 0s or more than limit consecutive 1s anywhere in the array.

For example, if limit = 2, then:

• [0,0] is valid
• [0,0,0] is invalid
• [1,1] is valid
• [1,1,1] is invalid

So the problem becomes:

Count all binary strings with exactly zero zeros and exactly one ones, where every consecutive run length is at most limit.

The constraints are:

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

This is a very important observation. Since both counts can reach 1000, the total length can be as large as 2000. A brute force enumeration of all binary arrays is completely infeasible because the number of possible arrays grows exponentially.

The constraints strongly suggest that we need a dynamic programming solution.

Several edge cases are important:

• limit = 1, meaning the array must strictly alternate
• One count being much larger than the other
• Cases where no valid array exists
• Cases where all arrangements are valid because limit is very large
• Large inputs near 1000, where efficiency matters significantly

Approaches

Brute Force Approach

A naive solution would generate every binary array containing exactly zero zeros and one ones, then check whether any consecutive run exceeds limit.

We could use backtracking:

• Place either 0 or 1
• Track how many zeros and ones remain
• Track the current consecutive run length
• Reject arrays violating the limit

This approach is correct because it explores every possible valid arrangement.

However, it is far too slow.

The total number of arrays is:

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

For values near 1000, this becomes astronomically large.

Even with pruning, the exponential growth makes this impossible.

Optimal Dynamic Programming Approach

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

• How many zeros have been used
• How many ones have been used
• Which value the array currently ends with

We do not need the entire array history.

Define:

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

To transition into dp0[i][j], we append a block of zeros of length k, where:

$$1 \le k \le limit$$

The previous state must end with 1.

Similarly for dp1[i][j].

The recurrence becomes:

$$dp0[i][j] = \sum_{k=1}^{limit} dp1[i-k][j]$$

$$dp1[i][j] = \sum_{k=1}^{limit} dp0[i][j-k]$$

Computing these sums directly would cost:

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

Since all values can be 1000, this may become too slow.

The optimization is to use prefix sums so each transition becomes constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(zero + one)	Generates every possible binary array
Optimal DP with Prefix Sums	O(zero × one)	O(zero × one)	Uses dynamic programming and sliding window transitions

Algorithm Walkthrough

Step 1: Define DP States

We maintain two DP tables:

• dp0[i][j], arrays with i zeros and j ones ending in 0
• dp1[i][j], arrays with i zeros and j ones ending in 1

These states are sufficient because validity only depends on the last run.

Step 2: Initialize Base Cases

If an array contains only zeros:

• It is valid only if the number of zeros is at most limit

So:

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

Similarly:

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

Step 3: Transition Into States Ending With 0

To compute dp0[i][j], append a consecutive block of zeros of length k.

The previous array must end in 1.

So:

$$dp0[i][j] = \sum_{k=1}^{limit} dp1[i-k][j]$$

Instead of recomputing the sum every time, we maintain prefix sums.

Step 4: Transition Into States Ending With 1

Similarly:

$$dp1[i][j] = \sum_{k=1}^{limit} dp0[i][j-k]$$

Again, prefix sums allow constant time transitions.

Step 5: Apply Modulo

All computations are done modulo:

$$10^9 + 7$$

because the number of valid arrays can become extremely large.

Step 6: Return Final Answer

The total number of valid arrays is:

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

modulo 10^9 + 7.

Why it works

The DP states completely characterize every valid partial array by tracking:

• how many zeros were used
• how many ones were used
• which digit appears at the end

Every valid array can be uniquely constructed by appending a final block of identical digits. Since each block length is constrained by limit, the transitions enumerate exactly all valid possibilities without duplicates or omissions.

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 i in range(1, min(zero, limit) + 1):
            dp0[i][0] = 1

        for j in range(1, min(one, limit) + 1):
            dp1[0][j] = 1

        # Fill DP tables
        for i in range(zero + 1):
            for j in range(one + 1):

                if i > 0:
                    val = dp1[i - 1][j]

                    if i - limit - 1 >= 0:
                        val -= dp1[i - limit - 1][j]

                    dp0[i][j] = (dp0[i - 1][j] + val) % MOD

                if j > 0:
                    val = dp0[i][j - 1]

                    if j - limit - 1 >= 0:
                        val -= dp0[i][j - limit - 1]

                    dp1[i][j] = (dp1[i][j - 1] + val) % MOD

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

The implementation uses two 2D DP arrays.

The first initialization handles arrays made entirely of zeros or entirely of ones. Such arrays are valid only if their length does not exceed limit.

The nested loops iterate through every (i, j) pair. Each state is computed using a sliding window recurrence.

The expression:

val = dp1[i - 1][j]

represents extending arrays ending in 1 by adding another 0.

If the consecutive zero run would exceed limit, we subtract the invalid contribution:

if i - limit - 1 >= 0:
    val -= dp1[i - limit - 1][j]

This effectively creates a prefix-sum style sliding window over valid transitions.

The same logic is mirrored for arrays ending in 1.

Finally, we sum both ending possibilities.

Go Solution

func numberOfStableArrays(zero int, one int, limit int) int {
	const MOD int = 1_000_000_007

	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 i := 1; i <= zero && i <= limit; i++ {
		dp0[i][0] = 1
	}

	for j := 1; j <= one && j <= limit; j++ {
		dp1[0][j] = 1
	}

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

			if i > 0 {
				val := dp1[i-1][j]

				if i-limit-1 >= 0 {
					val -= dp1[i-limit-1][j]
				}

				dp0[i][j] = (dp0[i-1][j] + val) % MOD

				if dp0[i][j] < 0 {
					dp0[i][j] += MOD
				}
			}

			if j > 0 {
				val := dp0[i][j-1]

				if j-limit-1 >= 0 {
					val -= dp0[i][j-limit-1]
				}

				dp1[i][j] = (dp1[i][j-1] + val) % MOD

				if dp1[i][j] < 0 {
					dp1[i][j] += MOD
				}
			}
		}
	}

	ans := (dp0[zero][one] + dp1[zero][one]) % MOD

	if ans < 0 {
		ans += MOD
	}

	return ans
}

The Go implementation closely mirrors the Python solution.

One important difference is modulo handling. In Go, negative modulo values remain negative, so after subtraction we explicitly add MOD back when needed.

Slices are used for the DP tables, and all memory is allocated up front.

Worked Examples

Example 1

Input:

zero = 1
one = 1
limit = 2

Possible arrays:

• [0,1]
• [1,0]

Both are valid.

DP States

i	j	dp0[i][j]	dp1[i][j]
1	0	1	0
0	1	0	1
1	1	1	1

Final answer:

$$1 + 1 = 2$$

Example 2

Input:

zero = 1
one = 2
limit = 1

No consecutive equal digits are allowed.

Possible arrangements:

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

DP Evolution

State	Value
dp0[1][1]	1
dp1[1][1]	1
dp1[1][2]	1

Final answer:

$$1$$

Example 3

Input:

zero = 3
one = 3
limit = 2

No run can exceed length 2.

The DP gradually builds all valid arrays while excluding any transition creating three consecutive equal digits.

Final count:

$$14$$

which matches the problem statement.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(zero × one)	Every DP state is computed once
Space	O(zero × one)	Two 2D DP tables are stored

The algorithm iterates through every pair (i, j) exactly once. Thanks to the sliding window optimization, each transition is constant time instead of iterating through all possible block lengths.

Without prefix-sum optimization, the complexity would become:

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

which is significantly slower for large inputs.

Test Cases

sol = Solution()

# Provided examples
assert sol.numberOfStableArrays(1, 1, 2) == 2  # simple two-element arrays
assert sol.numberOfStableArrays(1, 2, 1) == 1  # strict alternation
assert sol.numberOfStableArrays(3, 3, 2) == 14  # larger balanced example

# Small balanced cases
assert sol.numberOfStableArrays(2, 2, 2) == 6  # all permutations valid
assert sol.numberOfStableArrays(2, 2, 1) == 2  # only alternating arrays

# Single type within limit
assert sol.numberOfStableArrays(3, 0, 3) == 1  # all zeros valid
assert sol.numberOfStableArrays(0, 3, 3) == 1  # all ones valid

# Single type exceeding limit
assert sol.numberOfStableArrays(4, 0, 3) == 0  # too many consecutive zeros
assert sol.numberOfStableArrays(0, 4, 3) == 0  # too many consecutive ones

# Impossible alternation
assert sol.numberOfStableArrays(5, 1, 1) == 0  # impossible with strict alternation

# Tight limit
assert sol.numberOfStableArrays(2, 3, 1) == 1  # only one alternating arrangement

# Large limit
assert sol.numberOfStableArrays(2, 3, 10) == 10  # all combinations valid

# Minimal input
assert sol.numberOfStableArrays(1, 1, 1) == 2  # both alternating arrays valid

Test Summary

Test	Why
(1,1,2)	Smallest balanced example
(1,2,1)	Strict alternation constraint
(3,3,2)	Larger mixed example
(2,2,2)	Every arrangement valid
(2,2,1)	Alternating-only case
(3,0,3)	Single-value valid run
(4,0,3)	Single-value invalid run
(5,1,1)	Impossible construction
(2,3,10)	Very loose constraint
(1,1,1)	Minimal valid input

Edge Cases

One important edge case occurs when limit = 1. In this situation, no two adjacent values can be equal. The array must strictly alternate between 0 and 1. Many implementations accidentally allow repeated digits because they only check the total run length after construction. This implementation avoids that problem by encoding the constraint directly into the DP transitions.

Another critical edge case happens when one digit count is much larger than the other. For example:

zero = 5
one = 1
limit = 1

It is impossible to separate all zeros with only one 1, so the answer should be zero. The DP naturally handles this because no valid transition sequence can reach the final state.

A third important edge case is when all elements are the same. For example:

zero = 4
one = 0
limit = 3

This array is invalid because the consecutive run exceeds the limit. The base-case initialization correctly handles this by only setting states valid when the run length is at most limit.

Finally, large inputs near 1000 are especially important for performance. A naive triple-loop DP would be too slow. The sliding-window optimization ensures each state is computed in constant time, allowing the solution to scale efficiently within the problem constraints.