What is the primary pattern for solving the Find All Possible Stable Binary Arrays I problem?

The primary pattern is state transition dynamic programming, where each state represents the number of stable arrays with specific counts of 0's, 1's, and consecutive digits.

How do I optimize the space complexity for this problem?

You can reduce space complexity by using a sliding window technique to store only the previous and current DP states, instead of maintaining a full 4D DP table.

What is the time complexity of the best solution for this problem?

The time complexity of the best solution depends on the number of zeros, ones, and the limit, with an optimized approach achieving O(zero * one * limit).

How does the prefix sum optimization improve the solution?

Prefix sum optimization allows for faster state transitions by precomputing the counts, reducing the need for repeated calculations and improving overall time complexity.

What are the edge cases I should consider for this problem?

Consider edge cases such as a limit of 1, a limit of 0, or when the number of 0's or 1's is at its minimum or maximum allowed value.

#3129

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

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

给你 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 <= 200

lightbulb

解题思路

方法一：记忆化搜索

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

函数 $\textit{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$ 的情况 $\textit{dfs}(i - 1, j, 0)$ 和前一个数字是 $1$ 的情况 $\textit{dfs}(i - 1, j, 1)$ ，如果前一个数是 $0$ ，那么有可能使得子数组中有超过 $\textit{limit}$ 个 $0$ ，即不允许出现倒数第 $\textit{limit} + 1$ 个数是 $1$ 的情况，所以我们要减去这种情况，即 $\textit{dfs}(i - \textit{limit} - 1, j, 1)$ 。
如果 $k = 1$ ，我们考虑前一个数字是 $0$ 的情况 $\textit{dfs}(i, j - 1, 0)$ 和前一个数字是 $1$ 的情况 $\textit{dfs}(i, j - 1, 1)$ ，如果前一个数是 $1$ ，那么有可能使得子数组中有超过 $\textit{limit}$ 个 $1$ ，即不允许出现倒数第 $\textit{limit} + 1$ 个数是 $0$ 的情况，所以我们要减去这种情况，即 $\textit{dfs}(i, j - \textit{limit} - 1, 0)$ 。

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

时间复杂度 $O(\textit{zero} \times \textit{one})$ ，空间复杂度 $O(\textit{zero} \times \textit{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

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of dynamic programming and state transitions.
question_mark
Evaluate the candidate's ability to optimize both time and space complexity in a DP-based approach.
question_mark
Assess the candidate's ability to apply the prefix sum technique to optimize counting and state transitions.

warning

常见陷阱

外企场景

error
Forgetting to account for the consecutive identical digit limit while transitioning between states.
error
Not using the sliding window technique to optimize space complexity in larger test cases.
error
Inefficient transitions or recalculations leading to excessive time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Different limit values could be tested to assess the solution's ability to handle various stability constraints.
arrow_right_alt
The number of 0's and 1's could be varied to test the candidate's ability to handle different binary array sizes.
arrow_right_alt
Testing with edge cases, such as limit being 1 or 0, will assess the robustness of the candidate's solution.

help

常见问题

外企场景

继续练习

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