Problem Description

You need to count the number of stable binary arrays given three positive integers: zero, one, and limit.

A binary array arr is considered stable if it meets all three conditions:

1. It contains exactly zero number of 0s
2. It contains exactly one number of 1s
3. Every subarray with size greater than limit must contain both 0 and 1

The task is to find how many different stable binary arrays can be formed with these constraints. Since the result can be very large, return it modulo 10^9 + 7.

For example, if you have zero = 2, one = 1, and limit = 1, you need to create arrays with exactly 2 zeros and 1 one. The third condition means that any subarray of length greater than 1 must have both 0 and 1 in it. This prevents having consecutive runs of the same digit that are too long.

The solution uses dynamic programming with memoization. The function dfs(i, j, k) represents the number of valid arrays when there are i zeros and j ones remaining to place, with k indicating what the next element to place should be (0 or 1).

The key insight is that when placing a digit, we need to ensure we don't create a subarray of length limit + 1 containing only that digit. This is handled by subtracting invalid configurations where we would have more than limit consecutive identical digits.

Intuition

The key observation is that we need to build arrays where no consecutive sequence of the same digit exceeds limit in length. This suggests we should think about the problem recursively - at each position, we decide whether to place a 0 or 1, while keeping track of constraints.

Let's think about this step by step. When building a valid array, at any point we need to know:

• How many 0s we still need to place
• How many 1s we still need to place
• What digit we're about to place next

Why does the last point matter? Because if we're placing a 0, we need to ensure we don't create a run of 0s longer than limit. The same applies for 1s.

Now here's the clever part: instead of tracking the entire array built so far, we can use inclusion-exclusion principle. When we place a digit k, the total valid arrangements equals:

• All arrangements where we place k at this position
• MINUS the arrangements that would create an invalid run of length limit + 1

For example, if k = 0, we count all ways to place this 0 and continue building (dfs(i-1, j, 0) + dfs(i-1, j, 1)). But then we subtract cases where placing this 0 would create a run of limit + 1 consecutive 0s. This happens when the last limit + 1 positions are all 0s, which we can calculate as dfs(i - limit - 1, j, 1) - representing the state after placing limit + 1 zeros in a row.

The base cases are straightforward: when we have only one type of digit left, we can place them all consecutively only if their count doesn't exceed limit. Otherwise, we'd violate the constraint about maximum consecutive digits.

This approach elegantly handles the constraint without explicitly tracking consecutive counts, making the solution both efficient and clean.

Learn more about Dynamic Programming and Prefix Sum patterns.

Solution Approach

The solution uses memoization (dynamic programming with caching) to efficiently count valid stable arrays. Let's break down the implementation:

Core Function: dfs(i, j, k)

The function represents the number of stable arrays when:

• i = number of 0s remaining to place
• j = number of 1s remaining to place
• k = the next digit to place (0 or 1)

Base Cases

1. When only 1s remain (i = 0):

   • Return 1 if k = 1 and j ≤ limit (we can place all remaining 1s consecutively)
   • Otherwise return 0

2. When only 0s remain (j = 0):

   • Return 1 if k = 0 and i ≤ limit (we can place all remaining 0s consecutively)
   • Otherwise return 0

Recursive Cases with Inclusion-Exclusion

When placing a 0 (k = 0):

result = dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - invalid_cases

• dfs(i - 1, j, 0): Continue with another 0
• dfs(i - 1, j, 1): Switch to placing a 1
• Subtract invalid cases where we'd have limit + 1 consecutive 0s:
  • This occurs when i - limit - 1 ≥ 0
  • Invalid count = dfs(i - limit - 1, j, 1)

When placing a 1 (k = 1):

result = dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - invalid_cases

• dfs(i, j - 1, 0): Switch to placing a 0
• dfs(i, j - 1, 1): Continue with another 1
• Subtract invalid cases where we'd have limit + 1 consecutive 1s:
  • This occurs when j - limit - 1 ≥ 0
  • Invalid count = dfs(i, j - limit - 1, 0)

Final Answer

The total number of stable arrays is:

(dfs(zero, one, 0) + dfs(zero, one, 1)) % (10^9 + 7)

This accounts for arrays starting with either 0 or 1. The @cache decorator ensures each state is computed only once, giving us an efficient O(zero × one × 2) time complexity with O(zero × one × 2) space for memoization.

Example Walkthrough

Let's walk through a small example with zero = 2, one = 1, and limit = 1.

We need to find all arrays with exactly 2 zeros and 1 one, where no subarray of length > 1 can have only 0s or only 1s. This means we cannot have consecutive identical digits.

Starting the recursion:

• Total = dfs(2, 1, 0) + dfs(2, 1, 1)

Evaluating dfs(2, 1, 0) - placing a 0 first:

• We place a 0, leaving us with 1 zero and 1 one remaining
• Result = dfs(1, 1, 0) + dfs(1, 1, 1) - invalid_cases
• Since 2 - 1 - 1 = 0 ≥ 0, we subtract dfs(0, 1, 1) (placing 2 consecutive 0s)
• dfs(0, 1, 1): Only 1s remain, and we're placing a 1. Since 1 ≤ limit, return 1
• So: dfs(2, 1, 0) = dfs(1, 1, 0) + dfs(1, 1, 1) - 1

Evaluating dfs(1, 1, 0) - placing another 0:

• Result = dfs(0, 1, 0) + dfs(0, 1, 1) - invalid_cases
• Since 1 - 1 - 1 = -1 < 0, no invalid cases to subtract
• dfs(0, 1, 0): Only 1s remain but we're placing a 0, return 0
• dfs(0, 1, 1): Only 1s remain and we're placing a 1, return 1
• So: dfs(1, 1, 0) = 0 + 1 = 1

Evaluating dfs(1, 1, 1) - switching to place a 1:

• Result = dfs(1, 0, 0) + dfs(1, 0, 1) - invalid_cases
• Since 1 - 1 - 1 = -1 < 0, no invalid cases to subtract
• dfs(1, 0, 0): Only 0s remain and we're placing a 0, return 1
• dfs(1, 0, 1): Only 0s remain but we're placing a 1, return 0
• So: dfs(1, 1, 1) = 1 + 0 = 1

Back to dfs(2, 1, 0):

• dfs(2, 1, 0) = 1 + 1 - 1 = 1

Evaluating dfs(2, 1, 1) - placing a 1 first:

• Result = dfs(2, 0, 0) + dfs(2, 0, 1) - invalid_cases
• Since 1 - 1 - 1 = -1 < 0, no invalid cases to subtract
• dfs(2, 0, 0): Only 0s remain and we're placing a 0. Since 2 > limit, return 0
• dfs(2, 0, 1): Only 0s remain but we're placing a 1, return 0
• So: dfs(2, 1, 1) = 0 + 0 = 0

Final answer:

• Total = dfs(2, 1, 0) + dfs(2, 1, 1) = 1 + 0 = 1

The only valid array is [0, 1, 0], which satisfies all constraints:

• Has exactly 2 zeros and 1 one
• No two consecutive identical digits (respecting the limit of 1)

Solution Implementation

Time and Space Complexity

Time Complexity: O(zero * one * limit)

The time complexity is determined by the memoized recursive function dfs(i, j, k):

• Parameter i can take values from 0 to zero (inclusive), giving us zero + 1 possible values
• Parameter j can take values from 0 to one (inclusive), giving us one + 1 possible values
• Parameter k can only be 0 or 1, giving us 2 possible values

Each unique state (i, j, k) is computed at most once due to the @cache decorator. The total number of unique states is (zero + 1) * (one + 1) * 2.

However, when analyzing the recursive calls more carefully:

• Each state makes at most 3 recursive calls (2 additions and 1 subtraction)
• The subtraction involves jumping back by limit + 1 positions

The effective time complexity is O(zero * one) for the state space, but considering that each state might need to look back up to limit positions in certain cases, the overall time complexity is O(zero * one * limit).

Space Complexity: O(zero * one)

The space complexity consists of:

• Cache storage: The memoization cache stores all computed states. Since there are (zero + 1) * (one + 1) * 2 possible states, the cache requires O(zero * one) space
• Recursion stack: In the worst case, the recursion depth can go up to O(zero + one) when we traverse from (zero, one, k) down to base cases

The dominant factor is the cache storage, giving us a total space complexity of O(zero * one).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Understanding of the Inclusion-Exclusion Logic

The most common pitfall is misunderstanding why we subtract dfs(i - limit - 1, j, 1) when placing zeros (or the equivalent for ones). Many developers incorrectly think this represents "placing exactly limit+1 consecutive zeros," but it actually represents "having at least limit+1 consecutive zeros ending at the current position."

Why this matters: When we compute dfs(i-1, j, 0) + dfs(i-1, j, 1), we're counting all ways to build arrays. Some of these ways will violate the constraint by having limit+1 or more consecutive zeros. The subtraction removes these invalid configurations.

Solution: Think of it as: "If we place a zero now and had already placed limit zeros before this, we're creating an invalid sequence of limit+1 consecutive zeros. The number of such invalid sequences equals the number of ways to place the remaining elements after forcing limit+1 consecutive zeros."

2. Forgetting to Handle Negative Indices in Subtraction

A critical bug occurs when developers forget to check if i - limit - 1 >= 0 before subtracting invalid cases. Without this check, you might call dfs(-1, j, 1) which either causes an error or returns incorrect results.

Incorrect code:

# Missing boundary check - will cause errors!
total_ways -= count_arrays(zeros_left - limit - 1, ones_left, 1)

Correct code:

if zeros_left - limit - 1 >= 0:
    total_ways -= count_arrays(zeros_left - limit - 1, ones_left, 1)

3. Applying Modulo Operation Incorrectly

Another common mistake is applying the modulo operation at the wrong place or forgetting that subtraction can produce negative numbers in modular arithmetic.

Incorrect approach:

# This can produce negative results!
return (total_ways - invalid_cases) % MOD

Correct approach:

# Add MOD before taking modulo to handle negative results
return ((total_ways - invalid_cases) % MOD + MOD) % MOD

Or handle it at the final step only since Python handles negative modulo correctly:

# Python's modulo handles negatives correctly
result = (count_arrays(zero, one, 0) + count_arrays(zero, one, 1)) % MOD

4. Misunderstanding the Parameter k (last_element)

Some developers confuse k as "the element we just placed" rather than "the element we're about to place." This leads to inverted logic in the recursive calls.

Wrong interpretation: If k=0, we just placed a 0, so now we decide what to place next.

Correct interpretation: If k=0, we are about to place a 0, and the recursive calls determine what came before it in the array construction process.

5. Incorrect Base Cases

A subtle error is returning 1 whenever one type of digit runs out, without checking if the remaining digits can be placed consecutively within the limit.

Incorrect base case:

if zeros_left == 0:
    return 1  # Wrong! What if ones_left > limit?

Correct base case:

if zeros_left == 0:
    return 1 if (last_element == 1 and ones_left <= limit) else 0

The check ensures that:

• We're continuing with the same type of element (maintaining consistency)
• The remaining count doesn't exceed the limit for consecutive elements