Find All Possible Stable Binary Arrays II

Find All Possible Stable Binary Arrays II - Problem

You are tasked with constructing stable binary arrays - a fascinating combinatorial problem that tests your dynamic programming skills!

Given three positive integers zero, one, and limit, you need to count how many different binary arrays can be formed that satisfy these conditions:

The array contains exactly zero occurrences of 0
The array contains exactly one occurrences of 1
No subarray of length greater than limit can contain only 0s or only 1s (this ensures stability)

The third condition is the key constraint - it prevents long streaks of consecutive identical digits, making the array "stable" by ensuring diversity in longer subsequences.

Return the total number of such stable binary arrays. Since this number can be astronomically large, return it modulo 10⁹ + 7.

Example: If zero=1, one=1, limit=2, valid arrays are [0,1] and [1,0], so the answer is 2.

Input & Output

example_1.py — Basic Case

$ Input: zero = 1, one = 1, limit = 2

› Output: 2

💡 Note: With 1 zero and 1 one, we can form arrays [0,1] and [1,0]. Both are stable since no subarray longer than limit=2 contains only one type of digit. Total: 2 valid arrays.

example_2.py — Longer Array

$ Input: zero = 1, one = 2, limit = 1

› Output: 1

💡 Note: With limit=1, no two consecutive digits can be the same. The only valid arrangement is [0,1,0] - we must alternate. Arrays like [1,1,0] are invalid because '11' exceeds the limit.

example_3.py — Higher Limit

$ Input: zero = 3, one = 3, limit = 2

› Output: 14

💡 Note: With limit=2, we can have at most 2 consecutive 0s or 1s. This allows many more arrangements than alternating, but still prevents long streaks like '000' or '111'.

Constraints

1 ≤ zero, one ≤ 200
1 ≤ limit ≤ 200
Answer must be returned modulo 10⁹ + 7
Array length will be zero + one

Visualization

Tap to expand

Understanding the Visualization

Start Empty

Begin with an empty array and full quota of 0s and 1s

Make Valid Choices

At each position, choose 0 or 1 based on remaining quota and consecutive limit

Track Consecutive Count

Monitor how many consecutive identical digits we've placed

Use Memoization

Cache results for identical states to avoid redundant computation

Key Takeaway

🎯 Key Insight: Dynamic programming with state memoization transforms an exponential problem into a polynomial one by tracking only the essential information needed for future decisions.

Asked in

G Google 28 a Amazon 15 f Meta 12 ⊞ Microsoft 8

The optimal solution uses dynamic programming with memoization to count stable binary arrays. We track states as (zeros_left, ones_left, last_digit, consecutive_count) and recursively explore valid placements of 0s and 1s while respecting the limit constraint. The key insight is that we only need to track the count of consecutive identical digits at the end of our current array, not the entire array structure. This reduces the problem to manageable subproblems with polynomial time complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Generate All Arrays)	O((zero+one)! × (zero+one)²)	O((zero+one)!)	Generate all possible binary arrays and check stability condition
Dynamic Programming (Optimal)	O(zero × one × limit)	O(zero × one × limit)	Use memoized recursion to count valid arrangements efficiently

Brute Force (Generate All Arrays) — Algorithm Steps

Generate all permutations of arrays with exactly 'zero' 0s and 'one' 1s
For each array, check all subarrays of length > limit
Count arrays where every long subarray contains both 0 and 1
Return count modulo 10^9 + 7

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Create all possible arrangements of 0s and 1s

Check Stability

For each permutation, verify no long subarray is monochromatic

Count Valid

Increment counter for each stable array found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int isStable(int *arr, int len, int limit) {
    for (int i = 0; i < len; i++) {
        for (int j = i + limit + 1; j <= len; j++) {
            int hasZero = 0, hasOne = 0;
            for (int k = i; k < j; k++) {
                if (arr[k] == 0) hasZero = 1;
                else hasOne = 1;
            }
            if (!(hasZero && hasOne)) return 0;
        }
    }
    return 1;
}

int nextPermutation(int *arr, int len) {
    int i = len - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) i--;
    if (i < 0) return 0;
    
    int j = len - 1;
    while (arr[j] <= arr[i]) j--;
    
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    
    int left = i + 1, right = len - 1;
    while (left < right) {
        temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
    
    return 1;
}

int numberOfStableArrays(int zero, int one, int limit) {
    int len = zero + one;
    int *arr = (int*)malloc(len * sizeof(int));
    
    for (int i = 0; i < zero; i++) arr[i] = 0;
    for (int i = zero; i < len; i++) arr[i] = 1;
    
    qsort(arr, len, sizeof(int), compare);
    
    int validCount = 0;
    char **seen = (char**)malloc(1000000 * sizeof(char*));
    int seenCount = 0;
    
    do {
        if (isStable(arr, len, limit)) {
            validCount = (validCount + 1) % MOD;
        }
    } while (nextPermutation(arr, len));
    
    free(arr);
    return validCount;
}

int main() {
    int zero, one, limit;
    scanf("%d %d %d", &zero, &one, &limit);
    printf("%d\n", numberOfStableArrays(zero, one, limit));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((zero+one)! × (zero+one)²)

Factorial time to generate all permutations, then quadratic time to check each array

✓ Linear Growth

Space Complexity

O((zero+one)!)

Need to store all possible permutations

⚡ Linearithmic Space

26.5K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force (Generate All Arrays) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler