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 II

Number: 3407

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given three positive integers – zero, one, and limit – we want to count how many binary arrays exist that have exactly zero occurrences of 0 and one occurrences of 1, with the extra requirement that every contiguous subarray of size greater than limit must contain both 0 and 1. Equivalently, no run (i.e. consecutive block) of identical numbers can be longer than limit.

Key Insights

  • The “stability” condition forces that there is never a block of 0’s (or 1’s) longer than limit.
  • Since the array must contain exactly zero 0’s and one 1’s, and the runs cannot be too long, the problem is equivalent to counting the number of arrangements satisfying a “max consecutive identical elements” constraint.
  • A good way to solve this is to use dynamic programming where the state records the number of 0’s and 1’s used so far, the last digit added, and how many of that digit have appeared consecutively.
  • When adding the next element, if it is the same as the last, the current streak increases; if it is different, the streak resets to 1. In both cases, we must ensure that the streak never exceeds limit.

Space and Time Complexity

Time Complexity: O(zero * one * limit) – since for each combination of used 0’s and 1’s we may have up to 2 different “last digit” states and a streak count up to limit. Space Complexity: O(zero * one * limit) – needed to store the DP states either in a memoization table or iterative DP table.

Solution

We solve the problem using dynamic programming with recursion and memoization. We define a DP state as dp(z, o, last, streak) where: • z = the number of 0’s used so far, • o = the number of 1’s used so far, • last = the last digit placed (0 or 1), • streak = the count of consecutive occurrences of that last digit.

The recurrence works as follows: • If we have used all 0’s and 1’s then we have built a valid sequence. • Otherwise, we try to add a 0 (if available) and a 1 (if available).
  – If we add the same digit as last, then streak is increased (and must not exceed limit).
  – If we add a different digit, then the streak resets to 1. The final answer is obtained by summing over both valid starting moves (if available) and taking the result modulo 10^9+7.

Note that although the worst case seems high, many states may not be reached in practice and further optimizations (or even a combinatorial approach) may be applied in an interview discussion.

Code Solutions

MOD = 10**9 + 7
import sys
sys.setrecursionlimit(10**6)
from functools import lru_cache

# Recursive DP with memoization
@lru_cache(maxsize=None)
def dp(zero_used, one_used, last, streak):
    # If we have used all zeros and ones, we've formed a valid array.
    if zero_used == zero_total and one_used == one_total:
        return 1

    ways = 0
    # Option to add a 0 (if still available)
    if zero_used < zero_total:
        if last == 0:
            # same digit as last, so increment streak if we can add another 0 without breaking the limit
            if streak < limit:
                ways += dp(zero_used + 1, one_used, 0, streak + 1)
        else:  # switching from 1 to 0, so reset streak to 1
            ways += dp(zero_used + 1, one_used, 0, 1)
    # Option to add a 1 (if still available)
    if one_used < one_total:
        if last == 1:
            # if last is also 1, we can only add if streak < limit
            if streak < limit:
                ways += dp(zero_used, one_used + 1, 1, streak + 1)
        else:  # switching from 0 to 1
            ways += dp(zero_used, one_used + 1, 1, 1)
    return ways % MOD

# Main function: set the global limits then start the recursion.
def countStableArrays(zero, one, lim):
    global zero_total, one_total, limit
    zero_total, one_total, limit = zero, one, lim
    total_ways = 0
    # Start with a 0 if possible.
    if zero_total > 0:
        total_ways += dp(1, 0, 0, 1)
    # Start with a 1 if possible.
    if one_total > 0:
        total_ways += dp(0, 1, 1, 1)
    return total_ways % MOD

# Example usage:
if __name__ == "__main__":
    # Example 1: zero = 1, one = 1, limit = 2 -> Output: 2
    print(countStableArrays(1, 1, 2))
    # Example 2: zero = 1, one = 2, limit = 1 -> Output: 1
    print(countStableArrays(1, 2, 1))
    # Example 3: zero = 3, one = 3, limit = 2 -> Output: 14
    print(countStableArrays(3, 3, 2))
← Back to All Questions