3129. Find All Possible Stable Binary Arrays I Solution

Q: Is Find All Possible Stable Binary Arrays I easy or hard?

Find All Possible Stable Binary Arrays I is rated Medium difficulty. The challenge comes from designing the correct DP state and efficiently enforcing the limit on consecutive elements. Once the prefix sum optimization is understood, the implementation becomes straightforward.

Q: Find All Possible Stable Binary Arrays I Python/Java solution

Python implementations usually use dynamic programming with prefix sums and modular arithmetic for counting. Java versions follow the same DP structure with two tables tracking arrays ending in 0 or 1. Both implementations achieve O(zero × one) time complexity.

Q: How to solve Find All Possible Stable Binary Arrays I in O(n)?

A near-linear approach can be derived using combinatorics by counting valid ways to split zeros and ones into groups whose lengths do not exceed the limit. Using combinations with inclusion–exclusion removes configurations where a group exceeds the maximum size. With precomputed factorials, the counting can be done in roughly O(zero + one).

Q: What is the best approach for Find All Possible Stable Binary Arrays I?

Dynamic programming with prefix sum optimization is the most practical approach. It tracks arrays ending in 0 or 1 using states like dp0[i][j] and dp1[i][j], ensuring no more than limit consecutive elements are added. The method runs in O(zero × one) time and cleanly handles the consecutive constraint.

Q: Is Find All Possible Stable Binary Arrays I asked at Google/Amazon/Meta?

Problems involving constrained binary sequences and dynamic programming patterns frequently appear in interviews at companies like Amazon, Google, and Meta. The key skills tested are DP state design, prefix sum optimization, and counting valid configurations under constraints.

Q: What data structure is used in Find All Possible Stable Binary Arrays I?

The main structure is a 2D dynamic programming table that tracks counts of arrays ending with 0 or 1. Prefix sum arrays are used to speed up range-sum transitions when adding multiple consecutive elements. This combination keeps the algorithm efficient.

Q: What is the time complexity of Find All Possible Stable Binary Arrays I?

The standard dynamic programming solution runs in O(zero × one) time because every pair of zero and one counts is processed once. Prefix sums allow each transition to be computed in constant time. Space complexity is also O(zero × one) for the DP table.

The problem

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.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

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

Output: 2

Explanation:

The two possible stable binary arrays are [1,0] and [0,1], as both arrays have a single 0 and a single 1, and no subarray has a length greater than 2.

Example 2:

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

Output: 1

Explanation:

The only possible stable binary array is [1,0,1].

Note that the binary arrays [1,1,0] and [0,1,1] have subarrays of length 2 with identical elements, hence, they are not stable.

Example 3:

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

Output: 14

Explanation:

All the possible stable binary arrays are [0,0,1,0,1,1], [0,0,1,1,0,1], [0,1,0,0,1,1], [0,1,0,1,0,1], [0,1,0,1,1,0], [0,1,1,0,0,1], [0,1,1,0,1,0], [1,0,0,1,0,1], [1,0,0,1,1,0], [1,0,1,0,0,1], [1,0,1,0,1,0], [1,0,1,1,0,0], [1,1,0,0,1,0], and [1,1,0,1,0,0].

Constraints:

1 <= zero, one, limit <= 200

Approach overview

Problem Overview: You are given the number of 0s and 1s that must appear in a binary array and a limit restricting how many identical values can appear consecutively. The task is to count how many distinct arrays can be formed such that no more than limit consecutive 0s or 1s appear.

Approach 1: Combinatorics with Group Placement (Time: O(zero + one), Space: O(zero + one))

This approach models the array as alternating groups of 0s and 1s. Instead of building the array element by element, you count how many ways the required zeros and ones can be split into valid groups where each group length is ≤ limit. Using combinatorics (stars and bars with upper bounds), you compute the number of ways to distribute elements across groups while respecting the maximum run constraint. Inclusion–exclusion removes arrangements where a group exceeds the limit. This method works well when you precompute factorials and combinations modulo a constant. See related ideas in combinatorics.

Approach 2: Dynamic Programming with Prefix Sum Optimization (Time: O(zero × one), Space: O(zero × one))

The more direct method uses dynamic programming. Let dp0[i][j] be the number of valid arrays using i zeros and j ones that end with 0. Similarly, dp1[i][j] ends with 1. When placing a 0, the previous run must end with 1, and you can append between 1 and limit zeros as long as enough zeros remain. The same idea applies symmetrically for ones. Direct transitions would require iterating over all run lengths, which is expensive. Using prefix sums, you compute the sum of valid previous states in constant time, reducing the transition cost significantly.

The DP table iterates over all pairs (i, j). For each state, prefix sums allow you to subtract invalid ranges where the run length exceeds limit. This guarantees that no segment of identical values becomes longer than allowed while still counting every valid construction.

Recommended for interviews: The dynamic programming approach with prefix sums is the expected solution. It clearly models the constraint on consecutive elements and runs in O(zero × one) time, which fits typical constraints. The combinatorics approach is elegant and faster asymptotically but requires deeper mathematical reasoning and careful implementation of bounded distributions.

Approach 1: Using Combinatorics

This approach leverages combinatorial methods to generate all possible binary arrays and filters them based on the conditions using permutations.

First, consider the total length of the binary array as `zero + one`.
Next, generate all permutations of these positions and count only those satisfying the stability condition.
For handling larger arrays, remember to use modular arithmetic when calculating combinations or factorials.

Python

from math import factorial
MOD = 10**9 + 7

def stable_binary_arrays(zero, one, limit):
    total = zero + one
    stable_count = 0
    
    def nCr(n, r):
        return factorial(n) // (factorial(r) * factorial(n - r)) % MOD
    
    for i in range(max(zero, one), total - limit + 1):
        stable_count = (stable_count + nCr(total, i)) % MOD
    
    return stable_count

# Example Usage: stable_binary_arrays(3, 3, 2)

#include <stdio.h>
#define MOD 1000000007

long long factorial(int n) {
    if (n == 0) return 1;
    long long result = 1;
    for (int i = 1; i <= n; i++) {
        result = (result * i) % MOD;
    }
    return result;
}

long long nCr(int n, int r) {
    if (r > n) return 0;
    return factorial(n) / (factorial(r) * factorial(n - r)) % MOD;
}

int stable_binary_arrays(int zero, int one, int limit) {
    int total = zero + one;
    long long stable_count = 0;
    for (int i = (zero > one ? zero : one); i <= total - limit + 1; i++) {
        stable_count = (stable_count + nCr(total, i)) % MOD;
    }
    return stable_count;
}

// Example usage: stable_binary_arrays(3, 3, 2);

The function calculates all possible permutations using the nCr method (which calculates combinations). We iterate over possible starting positions for either 0 or 1, ensuring we maintain stability in subarrays of size greater than limit. The permutations are then summed to get the result.

Complexity

Time Complexity: O(n!) due to the permutations, where n = zero + one.
Space Complexity: O(1) for the constant space used by the calculation (since we're not storing arrays).

Try this approach in the editor

Approach 2: Dynamic Programming Approach

This method employs dynamic programming to solve the problem by building a solution that considers smaller subproblems of the main problem.

Define a DP table where dp[i][j] represents the number of ways to construct a stable array with `i` zeros and `j` ones.
Iterate over the table while respecting the stability condition for subarrays.
Base cases are initialized to reflect the constraints, and we return the final value from the DP table.

Java

public class StableBinaryArrays {
    private static final int MOD = 1000000007;
    public static int stableBinaryArrays(int zero, int one, int limit) {
        int[][] dp = new int[zero + 1][one + 1];
        dp[0][0] = 1;
        for (int i = 0; i <= zero; i++) {
            for (int j = 0; j <= one; j++) {
                if (i > 0) {
                    dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
                }
                if (j > 0) {
                    dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
                }
                if (i > limit) {
                    dp[i][j] = (dp[i][j] - dp[i - limit - 1][j] + MOD) % MOD;
                }
                if (j > limit) {
                    dp[i][j] = (dp[i][j] - dp[i][j - limit - 1] + MOD) % MOD;
                }
            }
        }
        return dp[zero][one];
    }
    
    // Example usage: stableBinaryArrays(3, 3, 2);
}

JavaScript

const MOD = 1000000007;
function stableBinaryArrays(zero, one, limit) {
    const dp = Array.from({ length: zero + 1 }, () => Array(one + 1).fill(0));
    dp[0][0] = 1;
    for (let i = 0; i <= zero; i++) {
        for (let j = 0; j <= one; j++) {
            if (i > 0) {
                dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
            }
            if (j > 0) {
                dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
            }
            if (i > limit) {
                dp[i][j] = (dp[i][j] - dp[i - limit - 1][j] + MOD) % MOD;
            }
            if (j > limit) {
                dp[i][j] = (dp[i][j] - dp[i][j - limit - 1] + MOD) % MOD;
            }
        }
    }
    return dp[zero][one];
}

// Example Usage: stableBinaryArrays(3, 3, 2);

Utilizing dynamic programming here allows us to solve the problem efficiently by building up from smaller cases. Each case in the DP table dp[i][j] is built using the previous results while ensuring subarray constraints are respected by subtracting overlapping cases.

Complexity

Time Complexity: O(zero * one) due to filling the DP table.
Space Complexity: O(zero * one) for storing the intermediate results in the DP table.

Try this approach in the editor

Approach 3: Memoized Search

We define a function dfs(i, j, k) to represent the number of stable binary arrays that satisfy the problem conditions when there are i zeros and j ones remaining to place, and the next digit to fill is k. Then the answer is dfs(zero, one, 0) + dfs(zero, one, 1).

The computation process of dfs(i, j, k) is as follows:

If i \lt 0 or j \lt 0, return 0.
If i = 0, then return 1 when k = 1 and j leq limit; otherwise return 0.
If j = 0, then return 1 when k = 0 and i leq limit; otherwise return 0.
If k = 0, we consider the case where the previous digit is 0, i.e., dfs(i - 1, j, 0), and the case where the previous digit is 1, i.e., dfs(i - 1, j, 1). If the previous digit is 0, there may be more than limit zeros in a subarray, which means the case where the (limit + 1)-th digit from the end is 1 is invalid, so we subtract this case: dfs(i - limit - 1, j, 1).
If k = 1, we consider the case where the previous digit is 0, i.e., dfs(i, j - 1, 0), and the case where the previous digit is 1, i.e., dfs(i, j - 1, 1). If the previous digit is 1, there may be more than limit ones in a subarray, which means the case where the (limit + 1)-th digit from the end is 0 is invalid, so we subtract this case: dfs(i, j - limit - 1, 0).

To avoid repeated computation, we use memoized search.

The time complexity is O(zero times one), and the space complexity is O(zero times one).

C++

class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        const int mod = 1e9 + 7;
        using ll = long long;
        vector<vector<array<ll, 2>>> f = vector<vector<array<ll, 2>>>(zero + 1, vector<array<ll, 2>>(one + 1, {-1, -1}));
        auto dfs = [&](this auto&& dfs, int i, int j, int k) -> ll {
            if (i < 0 || j < 0) {
                return 0;
            }
            if (i == 0) {
                return k == 1 && j <= limit;
            }
            if (j == 0) {
                return k == 0 && i <= limit;
            }
            ll& res = f[i][j][k];
            if (res != -1) {
                return res;
            }
            if (k == 0) {
                res = (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - dfs(i - limit - 1, j, 1) + mod) % mod;
            } else {
                res = (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - dfs(i, j - limit - 1, 0) + mod) % mod;
            }
            return res;
        };
        return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod;
    }
};

TypeScript

function numberOfStableArrays(zero: number, one: number, limit: number): number {
    const mod = 1e9 + 7;
    const f: number[][][] = Array.from({ length: zero + 1 }, () =>
        Array.from({ length: one + 1 }, () => [-1, -1]),
    );

    const dfs = (i: number, j: number, k: number): number => {
        if (i < 0 || j < 0) {
            return 0;
        }
        if (i === 0) {
            return k === 1 && j <= limit ? 1 : 0;
        }
        if (j === 0) {
            return k === 0 && i <= limit ? 1 : 0;
        }
        let res = f[i][j][k];
        if (res !== -1) {
            return res;
        }
        if (k === 0) {
            res = (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - dfs(i - limit - 1, j, 1) + mod) % mod;
        } else {
            res = (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - dfs(i, j - limit - 1, 0) + mod) % mod;
        }
        return (f[i][j][k] = res);
    };

    return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod;
}

func numberOfStableArrays(zero int, one int, limit int) int {
	const mod int = 1e9 + 7
	f := make([][][2]int, zero+1)
	for i := range f {
		f[i] = make([][2]int, one+1)
		for j := range f[i] {
			f[i][j] = [2]int{-1, -1}
		}
	}
	var dfs func(i, j, k int) int
	dfs = func(i, j, k int) int {
		if i < 0 || j < 0 {
			return 0
		}
		if i == 0 {
			if k == 1 && j <= limit {
				return 1
			}
			return 0
		}
		if j == 0 {
			if k == 0 && i <= limit {
				return 1
			}
			return 0
		}
		res := &f[i][j][k]
		if *res != -1 {
			return *res
		}
		if k == 0 {
			*res = (dfs(i-1, j, 0) + dfs(i-1, j, 1) - dfs(i-limit-1, j, 1) + mod) % mod
		} else {
			*res = (dfs(i, j-1, 0) + dfs(i, j-1, 1) - dfs(i, j-limit-1, 0) + mod) % mod
		}
		return *res
	}
	return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
}

Rust

impl Solution {
    pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
        const MOD: i64 = 1_000_000_007;

        fn dfs(
            i: i32,
            j: i32,
            k: usize,
            limit: i32,
            f: &mut Vec<Vec<[i64; 2]>>,
        ) -> i64 {
            if i < 0 || j < 0 {
                return 0;
            }

            if i == 0 {
                return if k == 1 && j <= limit { 1 } else { 0 };
            }

            if j == 0 {
                return if k == 0 && i <= limit { 1 } else { 0 };
            }

            let (iu, ju) = (i as usize, j as usize);

            if f[iu][ju][k] != -1 {
                return f[iu][ju][k];
            }

            let res = if k == 0 {
                (
                    dfs(i - 1, j, 0, limit, f)
                    + dfs(i - 1, j, 1, limit, f)
                    - dfs(i - limit - 1, j, 1, limit, f)
                    + MOD
                ) % MOD
            } else {
                (
                    dfs(i, j - 1, 0, limit, f)
                    + dfs(i, j - 1, 1, limit, f)
                    - dfs(i, j - limit - 1, 0, limit, f)
                    + MOD
                ) % MOD
            };

            f[iu][ju][k] = res;
            res
        }

        let mut f = vec![vec![[-1_i64; 2]; (one + 1) as usize]; (zero + 1) as usize];

        ((dfs(zero, one, 0, limit, &mut f) + dfs(zero, one, 1, limit, &mut f)) % MOD) as i32
    }
}

Try this approach in the editor

Approach 4: Dynamic Programming

We can also convert the memoized search in Solution 1 into dynamic programming.

We define f[i][j][k] as the number of stable binary arrays that use i zeros and j ones, with the last digit being k. Then the answer is f[zero][one][0] + f[zero][one][1].

Initially, we have f[i][0][0] = 1, where 1 leq i leq min(limit, zero); and f[0][j][1] = 1, where 1 leq j leq min(limit, one).

The state transition equations are as follows:

f[i][j][0] = f[i - 1][j][0] + f[i - 1][j][1] - f[i - limit - 1][j][1].
f[i][j][1] = f[i][j - 1][0] + f[i][j - 1][1] - f[i][j - limit - 1][0].

The time complexity is O(zero times one), and the space complexity is O(zero times one).

C++

class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        const int mod = 1e9 + 7;
        using ll = long long;
        ll f[zero + 1][one + 1][2];
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= min(zero, limit); ++i) {
            f[i][0][0] = 1;
        }
        for (int j = 1; j <= min(one, limit); ++j) {
            f[0][j][1] = 1;
        }
        for (int i = 1; i <= zero; ++i) {
            for (int j = 1; j <= one; ++j) {
                ll x = i - limit - 1 < 0 ? 0 : f[i - limit - 1][j][1];
                ll y = j - limit - 1 < 0 ? 0 : f[i][j - limit - 1][0];
                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod) % mod;
                f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod) % mod;
            }
        }
        return (f[zero][one][0] + f[zero][one][1]) % mod;
    }
};

TypeScript

function numberOfStableArrays(zero: number, one: number, limit: number): number {
    const mod = 1e9 + 7;
    const f: number[][][] = Array.from({ length: zero + 1 }, () =>
        Array.from({ length: one + 1 }, () => [0, 0]),
    );

    for (let i = 1; i <= Math.min(limit, zero); i++) {
        f[i][0][0] = 1;
    }
    for (let j = 1; j <= Math.min(limit, one); j++) {
        f[0][j][1] = 1;
    }

    for (let i = 1; i <= zero; i++) {
        for (let j = 1; j <= one; j++) {
            const x = i - limit - 1 < 0 ? 0 : f[i - limit - 1][j][1];
            const y = j - limit - 1 < 0 ? 0 : f[i][j - limit - 1][0];
            f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod) % mod;
            f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod) % mod;
        }
    }

    return (f[zero][one][0] + f[zero][one][1]) % mod;
}

func numberOfStableArrays(zero int, one int, limit int) int {
	const mod int = 1e9 + 7
	f := make([][][2]int, zero+1)
	for i := range f {
		f[i] = make([][2]int, one+1)
	}
	for i := 1; i <= min(zero, limit); i++ {
		f[i][0][0] = 1
	}
	for j := 1; j <= min(one, limit); j++ {
		f[0][j][1] = 1
	}
	for i := 1; i <= zero; i++ {
		for j := 1; j <= one; j++ {
			f[i][j][0] = (f[i-1][j][0] + f[i-1][j][1]) % mod
			if i-limit-1 >= 0 {
				f[i][j][0] = (f[i][j][0] - f[i-limit-1][j][1] + mod) % mod
			}
			f[i][j][1] = (f[i][j-1][0] + f[i][j-1][1]) % mod
			if j-limit-1 >= 0 {
				f[i][j][1] = (f[i][j][1] - f[i][j-limit-1][0] + mod) % mod
			}
		}
	}
	return (f[zero][one][0] + f[zero][one][1]) % mod
}

Rust

impl Solution {
    pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
        let mod_: i64 = 1_000_000_007;

        let zero = zero as usize;
        let one = one as usize;
        let limit = limit as usize;

        let mut f = vec![vec![[0_i64; 2]; one + 1]; zero + 1];

        for i in 1..=zero.min(limit) {
            f[i][0][0] = 1;
        }

        for j in 1..=one.min(limit) {
            f[0][j][1] = 1;
        }

        for i in 1..=zero {
            for j in 1..=one {
                let x = if i > limit { f[i - limit - 1][j][1] } else { 0 };
                let y = if j > limit { f[i][j - limit - 1][0] } else { 0 };

                f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod_) % mod_;
                f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod_) % mod_;
            }
        }

        ((f[zero][one][0] + f[zero][one][1]) % mod_) as i32
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Combinatorics	Time Complexity: `O(n!)` due to the permutations, where `n = zero + one`. Space Complexity: `O(1)` for the constant space used by the calculation (since we're not storing arrays).
Dynamic Programming Approach	Time Complexity: `O(zero * one)` due to filling the DP table. Space Complexity: `O(zero * one)` for storing the intermediate results in the DP table.
Memoized Search	–
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Combinatorics with Group Placement	O(zero + one)	O(zero + one)	When you want a math-driven counting approach and have combination precomputation available
Dynamic Programming with Prefix Sums	O(zero × one)	O(zero × one)	General case and most common interview solution

Frequently asked questions

Is Find All Possible Stable Binary Arrays I easy or hard?

Find All Possible Stable Binary Arrays I is rated Medium difficulty. The challenge comes from designing the correct DP state and efficiently enforcing the limit on consecutive elements. Once the prefix sum optimization is understood, the implementation becomes straightforward.

Find All Possible Stable Binary Arrays I Python/Java solution

Python implementations usually use dynamic programming with prefix sums and modular arithmetic for counting. Java versions follow the same DP structure with two tables tracking arrays ending in 0 or 1. Both implementations achieve O(zero × one) time complexity.

How to solve Find All Possible Stable Binary Arrays I in O(n)?

A near-linear approach can be derived using combinatorics by counting valid ways to split zeros and ones into groups whose lengths do not exceed the limit. Using combinations with inclusion–exclusion removes configurations where a group exceeds the maximum size. With precomputed factorials, the counting can be done in roughly O(zero + one).

What is the best approach for Find All Possible Stable Binary Arrays I?

Dynamic programming with prefix sum optimization is the most practical approach. It tracks arrays ending in 0 or 1 using states like dp0[i][j] and dp1[i][j], ensuring no more than limit consecutive elements are added. The method runs in O(zero × one) time and cleanly handles the consecutive constraint.

Is Find All Possible Stable Binary Arrays I asked at Google/Amazon/Meta?

Problems involving constrained binary sequences and dynamic programming patterns frequently appear in interviews at companies like Amazon, Google, and Meta. The key skills tested are DP state design, prefix sum optimization, and counting valid configurations under constraints.

What data structure is used in Find All Possible Stable Binary Arrays I?

The main structure is a 2D dynamic programming table that tracks counts of arrays ending with 0 or 1. Prefix sum arrays are used to speed up range-sum transitions when adding multiple consecutive elements. This combination keeps the algorithm efficient.

What is the time complexity of Find All Possible Stable Binary Arrays I?

The standard dynamic programming solution runs in O(zero × one) time because every pair of zero and one counts is processed once. Prefix sums allow each transition to be computed in constant time. Space complexity is also O(zero × one) for the DP table.

Find All Possible Stable Binary Arrays I solution and explanation

The problem

Approach overview

Approach 1: Using Combinatorics

Approach 2: Dynamic Programming Approach

Approach 3: Memoized Search

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find All Possible Stable Binary Arrays I solution and explanation

The problem

Approach overview

Approach 1: Using Combinatorics

Approach 2: Dynamic Programming Approach

Approach 3: Memoized Search

Approach 4: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems