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 <= 200This 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.
C
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.
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.
| Approach | Complexity |
|---|---|
| Using Combinatorics | Time Complexity: |
| Dynamic Programming Approach | Time Complexity: |
8 patterns to solve 80% Leetcode problems • Sahil & Sarra • 656,694 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