3130. Find All Possible Stable Binary Arrays II
Description
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
arris exactlyzero. - The number of occurrences of 1 in
arris exactlyone. - Each subarray of
arrwith a size greater thanlimitmust 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
Solutions
Solution 1: Memoization Search
We design a function $dfs(i, j, k)$ to represent the number of stable binary arrays that satisfy the problem conditions when there are $i$ $0$s and $j$ $1$s left, and the next number to be filled is $k$. The answer is $dfs(zero, one, 0) + dfs(zero, one, 1)$.
The calculation process of the function $dfs(i, j, k)$ is as follows:
If $i < 0$ or $j < 0$, return $0$.
If $i = 0$, return $1$ when $k = 1$ and $j \leq \textit{limit}$, otherwise return $0$.
If $j = 0$, return $1$ when $k = 0$ and $i \leq \textit{limit}$, otherwise return $0$.
If $k = 0$, we consider the case where the previous number is $0$, $dfs(i - 1, j, 0)$, and the case where the previous number is $1$, $dfs(i - 1, j, 1)$. If the previous number is $0$, it may cause more than $\textit{limit}$ $0$s in the subarray, i.e., the situation where the $\textit{limit} + 1$
Python3
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
@cache
def dfs(i: int, j: int, k: int) -> int:
if i == 0:
return int(k == 1 and j <= limit)
if j == 0:
return int(k == 0 and i <= limit)
if k == 0:
return (
dfs(i - 1, j, 0)
+ dfs(i - 1, j, 1)
- (0 if i - limit - 1 < 0 else dfs(i - limit - 1, j, 1))
)
return (
dfs(i, j - 1, 0)
+ dfs(i, j - 1, 1)
- (0 if j - limit - 1 < 0 else dfs(i, j - limit - 1, 0))
)
mod = 10**9 + 7
ans = (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
dfs.cache_clear()
return ans
Java
class Solution {
private final int mod = (int) 1e9 + 7;
private Long[][][] f;
private int limit;
public int numberOfStableArrays(int zero, int one, int limit) {
f = new Long[zero + 1][one + 1][2];
this.limit = limit;
return (int) ((dfs(zero, one, 0) + dfs(zero, one, 1)) % mod);
}
private long dfs(int i, int j, int k) {
if (i < 0 || j < 0) {
return 0;
}
if (i == 0) {
return k == 1 && j <= limit ? 1 : 0;
}
if (j == 0) {
return k == 0 && i <= limit ? 1 : 0;
}
if (f[i][j][k] != null) {
return f[i][j][k];
}
if (k == 0) {
f[i][j][k]
= (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - dfs(i - limit - 1, j, 1) + mod) % mod;
} else {
f[i][j][k]
= (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - dfs(i, j - limit - 1, 0) + mod) % mod;
}
return f[i][j][k];
}
}
C++
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
const int mod = 1e9 + 7;
using ll = long long;
vector<vector<array<ll, 2>>> f = vector<vector<array<ll, 2>>>(zero + 1, vector<array<ll, 2>>(one + 1, {-1, -1}));
auto dfs = [&](this auto&& dfs, int i, int j, int k) -> ll {
if (i < 0 || j < 0) {
return 0;
}
if (i == 0) {
return k == 1 && j <= limit;
}
if (j == 0) {
return k == 0 && i <= limit;
}
ll& res = f[i][j][k];
if (res != -1) {
return res;
}
if (k == 0) {
res = (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - dfs(i - limit - 1, j, 1) + mod) % mod;
} else {
res = (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - dfs(i, j - limit - 1, 0) + mod) % mod;
}
return res;
};
return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod;
}
};
Go
func numberOfStableArrays(zero int, one int, limit int) int {
const mod int = 1e9 + 7
f := make([][][2]int, zero+1)
for i := range f {
f[i] = make([][2]int, one+1)
for j := range f[i] {
f[i][j] = [2]int{-1, -1}
}
}
var dfs func(i, j, k int) int
dfs = func(i, j, k int) int {
if i < 0 || j < 0 {
return 0
}
if i == 0 {
if k == 1 && j <= limit {
return 1
}
return 0
}
if j == 0 {
if k == 0 && i <= limit {
return 1
}
return 0
}
res := &f[i][j][k]
if *res != -1 {
return *res
}
if k == 0 {
*res = (dfs(i-1, j, 0) + dfs(i-1, j, 1) - dfs(i-limit-1, j, 1) + mod) % mod
} else {
*res = (dfs(i, j-1, 0) + dfs(i, j-1, 1) - dfs(i, j-limit-1, 0) + mod) % mod
}
return *res
}
return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
}
Solution 2: Dynamic Programming
We can also convert the memoization search of Solution 1 into dynamic programming.
We define $f[i][j][k]$ as the number of stable binary arrays using $i$ $0$s and $j$ $1$s, and the last number is $k$. So 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(\textit{limit}, \textit{zero})$; and $f[0][j][1] = 1$, where $1 \leq j \leq \min(\textit{limit}, \textit{one})$.
The state transition equation is as follows:
$f[i][j][0] = f[i - 1][j][0] + f[i - 1][j][1] - f[i - \textit{limit} - 1][j][1]$.
$f[i][j][1] = f[i][j - 1][0] + f[i][j - 1][1] - f[i][j - \textit{limit} - 1][0]$.
The time complexity is $O(zero \times one)$, and the space complexity is $O(zero \times one)$.
Python3
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
mod = 10**9 + 7
f = [[[0, 0] for _ in range(one + 1)] for _ in range(zero + 1)]
for i in range(1, min(limit, zero) + 1):
f[i][0][0] = 1
for j in range(1, min(limit, one) + 1):
f[0][j][1] = 1
for i in range(1, zero + 1):
for j in range(1, one + 1):
x = 0 if i - limit - 1 < 0 else f[i - limit - 1][j][1]
y = 0 if j - limit - 1 < 0 else f[i][j - limit - 1][0]
f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x) % mod
f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y) % mod
return sum(f[zero][one]) % mod
Java
class Solution {
public int numberOfStableArrays(int zero, int one, int limit) {
final int mod = (int) 1e9 + 7;
long[][][] f = new long[zero + 1][one + 1][2];
for (int i = 1; i <= Math.min(zero, limit); ++i) {
f[i][0][0] = 1;
}
for (int j = 1; j <= Math.min(one, limit); ++j) {
f[0][j][1] = 1;
}
for (int i = 1; i <= zero; ++i) {
for (int j = 1; j <= one; ++j) {
long x = i - limit - 1 < 0 ? 0 : f[i - limit - 1][j][1];
long y = j - limit - 1 < 0 ? 0 : f[i][j - limit - 1][0];
f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod) % mod;
f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod) % mod;
}
}
return (int) ((f[zero][one][0] + f[zero][one][1]) % mod);
}
}
C++
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
const int mod = 1e9 + 7;
using ll = long long;
ll f[zero + 1][one + 1][2];
memset(f, 0, sizeof(f));
for (int i = 1; i <= min(zero, limit); ++i) {
f[i][0][0] = 1;
}
for (int j = 1; j <= min(one, limit); ++j) {
f[0][j][1] = 1;
}
for (int i = 1; i <= zero; ++i) {
for (int j = 1; j <= one; ++j) {
ll x = i - limit - 1 < 0 ? 0 : f[i - limit - 1][j][1];
ll y = j - limit - 1 < 0 ? 0 : f[i][j - limit - 1][0];
f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod) % mod;
f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod) % mod;
}
}
return (f[zero][one][0] + f[zero][one][1]) % mod;
}
};
Go
func numberOfStableArrays(zero int, one int, limit int) int {
const mod int = 1e9 + 7
f := make([][][2]int, zero+1)
for i := range f {
f[i] = make([][2]int, one+1)
}
for i := 1; i <= min(zero, limit); i++ {
f[i][0][0] = 1
}
for j := 1; j <= min(one, limit); j++ {
f[0][j][1] = 1
}
for i := 1; i <= zero; i++ {
for j := 1; j <= one; j++ {
f[i][j][0] = (f[i-1][j][0] + f[i-1][j][1]) % mod
if i-limit-1 >= 0 {
f[i][j][0] = (f[i][j][0] - f[i-limit-1][j][1] + mod) % mod
}
f[i][j][1] = (f[i][j-1][0] + f[i][j-1][1]) % mod
if j-limit-1 >= 0 {
f[i][j][1] = (f[i][j][1] - f[i][j-limit-1][0] + mod) % mod
}
}
}
return (f[zero][one][0] + f[zero][one][1]) % mod
}
TypeScript
function numberOfStableArrays(zero: number, one: number, limit: number): number {
const mod = 1e9 + 7;
const f: number[][][] = Array.from({ length: zero + 1 }, () =>
Array.from({ length: one + 1 }, () => [0, 0]),
);
for (let i = 1; i <= Math.min(limit, zero); i++) {
f[i][0][0] = 1;
}
for (let j = 1; j <= Math.min(limit, one); j++) {
f[0][j][1] = 1;
}
for (let i = 1; i <= zero; i++) {
for (let j = 1; j <= one; j++) {
const x = i - limit - 1 < 0 ? 0 : f[i - limit - 1][j][1];
const y = j - limit - 1 < 0 ? 0 : f[i][j - limit - 1][0];
f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - x + mod) % mod;
f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - y + mod) % mod;
}
}
return (f[zero][one][0] + f[zero][one][1]) % mod;
}