Watch 10 video solutions for Find All Possible Stable Binary Arrays I, a medium level problem involving Dynamic Programming, Prefix Sum. This walkthrough by codestorywithMIK has 17,576 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |