3129. Find All Possible Stable Binary Arrays I LeetCode Solution
In this guide, you will get 3129. Find All Possible Stable Binary Arrays I LeetCode Solution with the best time and space complexity. The solution to Find All Possible Stable Binary Arrays I problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find All Possible Stable Binary Arrays I
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 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.
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
Complexity Analysis
Time Complexity: O(mn)
Space Complexity: O(mn)
3129. Find All Possible Stable Binary Arrays I LeetCode Solution in C++
class Solution {
public:
// Same as 3129. Find All Possible Stable Binary Arrays I
int numberOfStableArrays(int zero, int one, int limit) {
constexpr int kMod = 1'000'000'007;
// dp[i][j][k] := the number of stable arrays, where the number of
// ocurrences of 0 is i and the number of ocurrences of 1 is j and the last
// number is k (0/1)
vector<vector<vector<long>>> dp(
zero + 1, vector<vector<long>>(one + 1, vector<long>(2)));
for (int i = 0; i <= min(zero, limit); ++i)
dp[i][0][0] = 1;
for (int j = 0; j <= min(one, limit); ++j)
dp[0][j][1] = 1;
for (int i = 1; i <= zero; ++i)
for (int j = 1; j <= one; ++j) {
dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1] -
(i - limit < 1 ? 0 : dp[i - limit - 1][j][1]) + kMod) %
kMod;
dp[i][j][1] = (dp[i][j - 1][0] + dp[i][j - 1][1] -
(j - limit < 1 ? 0 : dp[i][j - limit - 1][0]) + kMod) %
kMod;
}
return (dp[zero][one][0] + dp[zero][one][1]) % kMod;
}
}; /* code provided by PROGIEZ */
3129. Find All Possible Stable Binary Arrays I LeetCode Solution in Java
class Solution {
// Same as 3129. Find All Possible Stable Binary Arrays I
public int numberOfStableArrays(int zero, int one, int limit) {
final int kMod = 1_000_000_007;
// dp[i][j][k] := the number of stable arrays, where the number of
// occurrences of 0 is i and the number of occurrences of 1 is j and the last
// number is k (0/1)
long[][][] dp = new long[zero + 1][one + 1][2];
for (int i = 0; i <= Math.min(zero, limit); ++i)
dp[i][0][0] = 1;
for (int j = 0; j <= Math.min(one, limit); ++j)
dp[0][j][1] = 1;
for (int i = 1; i <= zero; ++i)
for (int j = 1; j <= one; ++j) {
dp[i][j][0] = (dp[i - 1][j][0] + dp[i - 1][j][1] -
(i - limit < 1 ? 0 : dp[i - limit - 1][j][1]) + kMod) %
kMod;
dp[i][j][1] = (dp[i][j - 1][0] + dp[i][j - 1][1] -
(j - limit < 1 ? 0 : dp[i][j - limit - 1][0]) + kMod) %
kMod;
}
return (int) ((dp[zero][one][0] + dp[zero][one][1]) % kMod);
}
} // code provided by PROGIEZ
3129. Find All Possible Stable Binary Arrays I LeetCode Solution in Python
class Solution:
# Same as 3129. Find All Possible Stable Binary Arrays I
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
kMod = 1_000_000_007
# dp[i][j][k] := the number of stable arrays, where the number of
# occurrences of 0 is i and the number of occurrences of 1 is j and the last
# number is k (0/1)
dp = [[[0] * 2
for _ in range(one + 1)]
for _ in range(zero + 1)]
for i in range(min(zero, limit) + 1):
dp[i][0][0] = 1
for j in range(min(one, limit) + 1):
dp[0][j][1] = 1
for i in range(1, zero + 1):
for j in range(1, one + 1):
dp[i][j][0] = (
dp[i - 1][j][0] + dp[i - 1][j][1] -
(dp[i - limit - 1][j][1] if i - limit >= 1 else 0) + kMod) % kMod
dp[i][j][1] = (
dp[i][j - 1][0] + dp[i][j - 1][1] -
(dp[i][j - limit - 1][0] if j - limit >= 1 else 0) + kMod) % kMod
return (dp[zero][one][0] + dp[zero][one][1]) % kMod # code by PROGIEZ
