What is a stable binary array in this problem?

A stable binary array has at most 'limit' consecutive zeros or ones and uses exactly the given counts of zeros and ones.

How does the state transition DP work here?

Each dp[x][y][z] counts arrays with x zeros, y ones remaining, and last element z, updating by adding up to 'limit' consecutive zeros or ones from opposite ending states.

Can this approach handle large zero and one values efficiently?

Yes, using prefix sums reduces repeated summation in transitions, making it feasible for large counts within constraints.

Are all permutations of zeros and ones considered?

Only permutations respecting the consecutive limit and exact counts of zeros and ones are included in the total.

Does GhostInterview provide ready-made solution checks?

Yes, it verifies the DP transitions and total count against examples to prevent undercounting or misapplying the consecutive limit.

#3130

Hard

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

找出所有稳定的二进制数组 II

给你 3 个正整数 zero ， one 和 limit 。一个二进制数组 arr 如果满足以下条件，那么我们称它是稳定的： 0 在 arr 中出现次数恰好为 zero 。 1 在 arr 中出现次数恰好为 one 。 arr 中每个长度超过 limit 的子数组都同时包含 …

动态规划前缀和

题目描述

给你 3 个正整数 zero ，one 和 limit 。

一个二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：

0 在 arr 中出现次数恰好为 zero 。
1 在 arr 中出现次数恰好为 one 。
arr 中每个长度超过 limit 的子数组都同时包含 0 和 1 。

请你返回稳定二进制数组的总数目。

由于答案可能很大，将它对 10⁹ + 7 取余后返回。

示例 1：

输入：zero = 1, one = 1, limit = 2

输出：2

解释：

两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。

示例 2：

输入：zero = 1, one = 2, limit = 1

输出：1

解释：

唯一稳定的二进制数组是 [1,0,1] 。

二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。

示例 3：

输入：zero = 3, one = 3, limit = 2

输出：14

解释：

所有稳定的二进制数组包括 [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] 和 [1,1,0,1,0,0] 。

提示：

1 <= zero, one, limit <= 1000

lightbulb

解题思路

方法一：记忆化搜索

我们设计一个函数 $dfs(i, j, k)$ 表示还剩下 $i$ 个 $0$ 和 $j$ 个 $1$ 且接下来待填的数字是 $k$ 的情况下，满足题目条件的稳定二进制数组的个数。那么答案就是 $dfs(zero, one, 0) + dfs(zero, one, 1)$ 。

函数 $dfs(i, j, k)$ 的计算过程如下：

如果 $i \lt 0$ 或 $j \lt 0$ ，返回 $0$ 。
如果 $i = 0$ ，那么当 $k = 1$ 且 $j \leq \textit{limit}$ 时返回 $1$ ，否则返回 $0$ 。
如果 $j = 0$ ，那么当 $k = 0$ 且 $i \leq \textit{limit}$ 时返回 $1$ ，否则返回 $0$ 。
如果 $k = 0$ ，我们考虑前一个数字是 $0$ 的情况 $dfs(i - 1, j, 0)$ 和前一个数字是 $1$ 的情况 $dfs(i - 1, j, 1)$ ，如果前一个数是 $0$ ，那么有可能使得子数组中有超过 $\textit{limit}$ 个 $0$ ，即不允许出现倒数第 $\textit{limit} + 1$ 个数是 $1$ 的情况，所以我们要减去这种情况，即 $dfs(i - \textit{limit} - 1, j, 1)$ 。
如果 $k = 1$ ，我们考虑前一个数字是 $0$ 的情况 $dfs(i, j - 1, 0)$ 和前一个数字是 $1$ 的情况 $dfs(i, j - 1, 1)$ ，如果前一个数是 $1$ ，那么有可能使得子数组中有超过 $\textit{limit}$ 个 $1$ ，即不允许出现倒数第 $\textit{limit} + 1$ 个数是 $0$ 的情况，所以我们要减去这种情况，即 $dfs(i, j - \textit{limit} - 1, 0)$ 。

为了避免重复计算，我们使用记忆化搜索的方法。

时间复杂度 $O(zero \times one)$ ，空间复杂度 $O(zero \times one)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

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

speed

复杂度分析

指标	值
时间	and space depend on zero, one, and limit values. Filling dp[x][y][z] for all combinations gives O(zero _one_ limit) in naive form, optimized with prefix sums for practical performance.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expecting recognition of state representation dp[x][y][z] for exact zero and one counts.
question_mark
Prefers seeing prefix sum optimization to handle consecutive limit efficiently.
question_mark
Looking for awareness of transition constraints when adding multiple zeros or ones at once.

warning

常见陷阱

外企场景

error
Failing to enforce the consecutive limit correctly in DP transitions.
error
Ignoring one ending state when summing total stable arrays, undercounting results.
error
Incorrect indexing or off-by-one errors in prefix sums for multiple consecutive elements.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Change the consecutive limit dynamically per element type.
arrow_right_alt
Count stable arrays without fixing exact numbers of zeros or ones.
arrow_right_alt
Generalize to ternary or higher base arrays with similar stability constraints.

help

常见问题

外企场景

继续练习

#3129 找出所有稳定的二进制数组 I #3077 K 个不相交子数组的最大能量值 #3225 网格图操作后的最大分数