You are given 3 positive integers zero, one, and limit.
A binary array arr is called stable if:
arr is exactly zero.arr is exactly one.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 109 + 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 <= 200Problem 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.
This approach leverages combinatorial methods to generate all possible binary arrays and filters them based on the conditions using permutations.
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.
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).
This method employs dynamic programming to solve the problem by building a solution that considers smaller subproblems of the main problem.
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.
Java
JavaScript
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.
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:
i \lt 0 or j \lt 0, return 0.i = 0, then return 1 when k = 1 and j leq limit; otherwise return 0.j = 0, then return 1 when k = 0 and i leq limit; otherwise return 0.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).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).
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).
| Approach | Complexity |
|---|---|
| Using Combinatorics | Time Complexity: |
| Dynamic Programming Approach | Time Complexity: |
| Memoized Search | — |
| Dynamic Programming | — |
| 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 |
Find All Possible Stable Binary Arrays I | 2 Approaches | Detailed Intuition | Leetcode 3129 | MIK • codestorywithMIK • 17,576 views views
Watch 9 more video solutions →Practice Find All Possible Stable Binary Arrays I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor