We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find All Possible Stable Binary Arrays I

Number: 3406

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given three positive integers zero, one, and limit, count how many binary arrays (arrays consisting of only 0’s and 1’s) of length (zero + one) exist that use exactly zero zeros and one ones and satisfy the following condition: every contiguous subarray longer than limit must contain both 0 and 1. In other words, the array is called “stable” if no block of consecutive identical elements (0 or 1) has length greater than limit. Return the count modulo 10^9+7.

Key Insights

  • The subarray condition is equivalent to ensuring that no more than limit consecutive 0’s or 1’s occur in the array.
  • The problem becomes counting the number of ways to interleave exactly zero zeros and one ones while restricting the maximum run length of each digit.
  • A dynamic programming approach can be used where the state tracks the number of 0’s and 1’s used so far, the last placed element, and the length of its current run.
  • Resetting the run counter occurs when switching the digit (from 0 to 1 or from 1 to 0).

Space and Time Complexity

Time Complexity: O(zero * one * limit * 2), since we consider each possible state defined by the count of zeros, ones, last digit, and current run length. Space Complexity: O(zero * one * limit * 2) due to the memoization or DP table storage.

Solution

We use a recursive dynamic programming approach with memoization. The recursion state is represented by:

  • the number of zeros used so far,
  • the number of ones used so far,
  • the last digit appended (either 0 or 1, or undefined at the start),
  • the current run length of that last digit.

For each state, we try to extend the array by appending a 0 or a 1 if possible under the limit constraint. When switching digits, the run length resets to 1. When continuing with the same digit, we only proceed if the current run length is less than limit. Our recursive function returns the count of valid completions from that state, and we add the results modulo 10^9+7. Iterative DP or bottom-up approaches are also possible. The trick is to notice that the problem is constrained by maximum consecutive repeats, and counting arrangements is a typical application of DP with state involving the current run length.

Code Solutions

# Python solution with line-by-line comments
MOD = 10**9 + 7

def countStableArrays(zero, one, limit):
    # dp memoization cache: key is (zeros_used, ones_used, last_digit, run_length)
    memo = {}
    
    def dp(zeros_used, ones_used, last_digit, run_count):
        # if we've used exactly all zeros and ones, we found a stable array
        if zeros_used == zero and ones_used == one:
            return 1
        # Check if this state has been computed before
        key = (zeros_used, ones_used, last_digit, run_count)
        if key in memo:
            return memo[key]
        
        count = 0  # count valid arrays from this state
        
        # Option 1: add a '0' if possible
        if zeros_used < zero:
            # If last_digit is not 0 (or starting state), reset run to 1
            if last_digit != 0:
                count += dp(zeros_used + 1, ones_used, 0, 1)
            else:
                # Continue with '0' only if run_count is less than limit
                if run_count < limit:
                    count += dp(zeros_used + 1, ones_used, 0, run_count + 1)
        
        # Option 2: add a '1' if possible
        if ones_used < one:
            if last_digit != 1:
                count += dp(zeros_used, ones_used + 1, 1, 1)
            else:
                if run_count < limit:
                    count += dp(zeros_used, ones_used + 1, 1, run_count + 1)
        
        # Store the computed result modulo MOD
        memo[key] = count % MOD
        return memo[key]
    
    # Start with undefined last_digit (None) and run_count 0
    return dp(0, 0, None, 0)

# Example usage:
print(countStableArrays(1, 1, 2))  # Output: 2
print(countStableArrays(1, 2, 1))  # Output: 1
print(countStableArrays(3, 3, 2))  # Output: 14
← Back to All Questions