Watch 10 video solutions for Find All Possible Stable Binary Arrays II, a hard level problem involving Dynamic Programming, Prefix Sum. This walkthrough by NeetCode has 551,948 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].
Example 2:
Input: zero = 1, one = 2, limit = 1
Output: 1
Explanation:
The only possible stable binary array is [1,0,1].
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 <= 1000