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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find All Possible Stable Binary Arrays I

Difficulty: Medium

Problem Description

You are given 3 positive integers zero, one, and limit. A binary array arr is called stable if:

  • The number of occurrences of 0 in arr is exactly zero.
  • The number of occurrences of 1 in arr is exactly one.
  • Each subarray of arr with a size greater than limit must contain both 0 and 1.

Return the total number of stable binary arrays modulo 10^9 + 7.

Key Insights

  • A stable binary array must have a specific arrangement of 0s and 1s to avoid violating the subarray condition.
  • The placement of 1s must be strategized to ensure that no segment longer than limit contains only 0s or only 1s.
  • The problem can be approached using dynamic programming to count valid distributions of 0s and 1s.

Space and Time Complexity

Time Complexity: O(zero * one)
Space Complexity: O(zero + one)

Solution

To solve this problem, we can use dynamic programming. We will create a table dp[i][j] where i represents the count of 0s used so far and j represents the count of 1s used. The value at dp[i][j] will represent the number of stable binary arrays that can be formed with i 0s and j 1s.

The algorithm will:

  1. Initialize a dynamic programming table.
  2. Iterate through each possible count of 0s and 1s.
  3. For each combination of 0s and 1s, calculate the number of valid arrangements based on previous counts.
  4. Ensure that the conditions for stability (subarray length) are met.
  5. Return the total count of stable arrays modulo 10^9 + 7.

Code Solutions

MOD = 10**9 + 7

def countStableArrays(zero, one, limit):
    # dp[i][j] will be the number of stable arrays formed with i 0's and j 1's
    dp = [[0] * (one + 1) for _ in range(zero + 1)]
    dp[0][0] = 1  # Base case: one way to form an empty array

    for i in range(zero + 1):
        for j in range(one + 1):
            if i + j == 0:
                continue  # Skip the empty case
            # Adding a '0'
            if i > 0:
                dp[i][j] += dp[i - 1][j] * (j + 1) % MOD
            # Adding a '1'
            if j > 0:
                dp[i][j] += dp[i][j - 1] * (i + 1) % MOD
            dp[i][j] %= MOD

    return dp[zero][one]

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