3129. Find All Possible Stable Binary Arrays I

MediumDynamic ProgrammingPrefix Sum

Leetcode Link

Problem 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 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 (10^9 + 7).

Intuition

The problem asks for counting binary arrays that meet specific conditions on the number of 0s and 1s and the composition of subarrays beyond a certain size. This naturally lends itself to a dynamic programming or recursive solution, where we attempt to build the solution progressively while ensuring stability at every step.

To solve this, we employ a memoization technique combined with depth-first search (DFS). We define a recursive function dfs(i, j, k), where:

i indicates how many 0s are left to place.
j indicates how many 1s are left to place.
k indicates the next number to be placed, either 0 or 1.

The recursive formulation is structured as follows:

When i is 0, we can only place 1s, and we check if placing them maintains the stability requirement.
When j is 0, only 0s can be placed, similarly ensuring the stability condition is met.
If k is 0, we need to evaluate two scenarios:
1. The previous number placed could be 0, giving rise to a call dfs(i - 1, j, 0).
2. The previous number could have been 1, leading to a call dfs(i - 1, j, 1).
For the stable condition, if placing another 0 would cause a subarray of more than limit length to consist solely of 0s, we must backtrack and remove the invalid count.

By memoizing these subproblems, we effectively manage the potential overlap and ensure efficiency. The final result is derived by combining the counts from initiating with either a 0 or a 1, modulo (10^9 + 7).

Learn more about Dynamic Programming and Prefix Sum patterns.

Solution Approach

The solution employs a dynamic programming approach through memoization combined with depth-first search to efficiently count the number of stable binary arrays. Here's a breakdown of the implemented algorithm:

Recursive Function Definition:
- We define a recursive function dfs(i, j, k):
  - i represents the remaining count of 0s to place.
  - j represents the remaining count of 1s to place.
  - k indicates the type of number to be placed next (0 or 1).
Base Conditions:
- If i is 0, meaning we have no more 0s to place, check if placing only 1s would violate the subarray limit constraint. Only return a count if placing the remaining 1s directly is valid.
- If j is 0, verify if placing only 0s doesn't breach the subarray constraint. Return a count only if valid placement of the remaining 0s is feasible.
Recursive Case:
- When the next number to place is 0 (k = 0):
  - Call dfs(i - 1, j, 0) for placing another 0.
  - Call dfs(i - 1, j, 1) for placing a 1 instead and switching the number type.
  - Adjust counts to ensure that any longer subarrays formed do not contain more than limit consecutive 0s by subtracting unnecessary recursive calls.
- When the next number to be placed is 1 (k = 1), employ a similar strategy:
  - Call dfs(i, j - 1, 0) and dfs(i, j - 1, 1).
  - Ensure not exceeding limit consecutive 1s in the subarrays by adjusting recursion results.
Memoization:
- The @cache decorator is utilized to store previously computed results for specific states (i, j, k), reducing redundant computations and improving efficiency.
Final Result:
- The solution is computed by adding results from starting with either 0 or 1: (dfs(zero, one, 0) + dfs(zero, one, 1)) % (10^9 + 7) to account for large numbers.
- Clear the cache post calculation with dfs.cache_clear() to avoid memory issues.

The algorithm carefully constructs all possible binary arrays adhering to the given constraints, leveraging memoization to ensure efficiency in handling overlapping subproblems.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to understand the solution approach for counting stable binary arrays. Suppose we have:

zero = 2: The binary array must contain exactly 2 zeros.
one = 2: The binary array must contain exactly 2 ones.
limit = 2: Any subarray longer than 2 elements must contain both 0 and 1.

Our goal is to count all possible "stable" binary arrays meeting these criteria.

Step-by-step Breakdown:

Initial State: We start by considering two primary options: beginning the array with either a 0 or a 1.
Recursive Exploration:
- Starting with 0:
  1. Place a 0, resulting in one less zero to place. This leads us into state (1, 2, 1), where 1 denotes the next number should be 1.
  2. Follow with a 1, resulting in state (1, 1, 0). Now we have one 0 and one 1 remaining.
  3. We now consider the placements from two possible endings:
    - Follow with another 0, reaching (0, 1, 1).
    - Or a 1, resulting in (1, 0, 0).
  4. Check each case:
    - If (0, 1, 1): Only a 1 can be placed next, consistent with ending the array, fulfilling stability.
    - If (1, 0, 0): Only a 0 can be placed next; this satisfies stability.
- Starting with 1:
  1. Place a 1 to reach state (2, 1, 0).
  2. Place a 0, resulting in (1, 1, 1).
  3. Continue by ending with placements from two options:
    - Follow with another 1, reaching (1, 0, 0).
    - Or a 0, leading to (0, 1, 1).
  4. Verify each arrangement:
    - For (1, 0, 0): A 0 can be placed next respectfully attaining stability.
    - For (0, 1, 1): Place a 1 respecting the constraints.
Memoization and Counting: Each transition point along these paths is cached. It avoids recomputing identical states, streamlines solving.
Result Aggregation: Finally, the number of valid stable arrays is derived by combining outcomes starting with 0 or 1. Each sum is taken modulo (10^9 + 7).

For this example, valid stable arrays can be [0, 1, 0, 1], [0, 1, 1, 0], [1, 0, 1, 0], and [1, 0, 0, 1]. Using the recursive and memoized approach efficiently evaluates all feasible configurations.

Solution Implementation

1from functools import cache
2
3class Solution:
4    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
5        # Memoized recursive function to find the number of stable arrays
6        @cache
7        def dfs(i: int, j: int, k: int) -> int:
8            # Base case: if no zeros left, check if the remaining ones fit within the limit
9            if i == 0:
10                return int(k == 1 and j <= limit)
11            # Base case: if no ones left, check if the remaining zeros fit within the limit
12            if j == 0:
13                return int(k == 0 and i <= limit)
14          
15            # Case when the last added element is zero
16            if k == 0:
17                # Possible next steps: add zero or add one, subtract over-counted solutions
18                return (
19                    dfs(i - 1, j, 0)  # Add another zero
20                    + dfs(i - 1, j, 1)  # Switch to adding one
21                    - (0 if i - limit - 1 < 0 else dfs(i - limit - 1, j, 1))  # Adjust for constraint violations
22                )
23          
24            # Case when the last added element is one
25            return (
26                dfs(i, j - 1, 0)  # Add a zero
27                + dfs(i, j - 1, 1)  # Add another one
28                - (0 if j - limit - 1 < 0 else dfs(i, j - limit - 1, 0))  # Adjust for constraint violations
29            )
30
31        mod = 10**9 + 7  # Define the modulus for the final answer
32        # Calculate the number of stable arrays starting with either a zero or a one
33        ans = (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
34        dfs.cache_clear()  # Clear cache after computation
35        return ans
36

1class Solution {
2    private static final int MOD = (int) 1e9 + 7; // constant for modulo computations
3    private Long[][][] dp; // memoization array
4    private int limit;
5
6    /**
7     * Computes the number of stable arrays consisting of a given number of zeros and ones,
8     * with a specific subsequence length limit.
9     *
10     * @param zero number of zero elements available
11     * @param one number of one elements available
12     * @param limit maximum length of subsequence consisting of all 1s or all 0s
13     * @return number of stable arrays that can be formed
14     */
15    public int numberOfStableArrays(int zero, int one, int limit) {
16        dp = new Long[zero + 1][one + 1][2]; // initialize the memoization array
17        this.limit = limit; // store limit for use in recursive method
18        // Compute results starting with either 0 or 1 and sum them
19        return (int) ((dfs(zero, one, 0) + dfs(zero, one, 1)) % MOD);
20    }
21
22    /**
23     * Recursive helper function with memoization to count stable arrays.
24     *
25     * @param i remaining zero elements
26     * @param j remaining one elements
27     * @param k last element type (0 for zero, 1 for one)
28     * @return number of stable arrays that can be formed
29     */
30    private long dfs(int i, int j, int k) {
31        // If more zeros or ones than available, return 0
32        if (i < 0 || j < 0) {
33            return 0;
34        }
35        // Base case: check if it's valid to end with a 1 and enough 1s for spacing
36        if (i == 0) {
37            return k == 1 && j <= limit ? 1 : 0;
38        }
39        // Base case: check if it's valid to end with a 0 and there are enough 0s
40        if (j == 0) {
41            return k == 0 && i <= limit ? 1 : 0;
42        }
43        // If already computed, return cached value
44        if (dp[i][j][k] != null) {
45            return dp[i][j][k];
46        }
47        // Calculate possible arrays:
48        // If last number is a 0, decrement zero count and consider both next options
49        if (k == 0) {
50            dp[i][j][k]
51                = (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - dfs(i - limit - 1, j, 1) + MOD) % MOD;
52        } 
53        // If last number is a 1, decrement one count and consider both next options
54        else {
55            dp[i][j][k]
56                = (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - dfs(i, j - limit - 1, 0) + MOD) % MOD;
57        }
58        return dp[i][j][k];
59    }
60}
61

1#include <vector>
2#include <array>
3
4class Solution {
5public:
6    int numberOfStableArrays(int zero, int one, int limit) {
7        const int MODULO = 1e9 + 7; // Define the modulo for results
8        using ll = long long; // Define an alias for long long
9
10        // Initialize a 3D vector to store intermediate results for the dynamic programming approach
11        std::vector<std::vector<std::array<ll, 2>>> dp(zero + 1, std::vector<std::array<ll, 2>>(one + 1, { -1, -1 }));
12
13        // Recursive lambda for depth-first search with memoization
14        auto dfs = [&](auto &&dfs, int remainingZeros, int remainingOnes, int currentState) -> ll {
15            if (remainingZeros < 0 || remainingOnes < 0) {
16                return 0; // Base case: negative indices are invalid
17            }
18            if (remainingZeros == 0) {
19                return currentState == 1 && remainingOnes <= limit; // Check if current state satisfies the limit
20            }
21            if (remainingOnes == 0) {
22                return currentState == 0 && remainingZeros <= limit; // Check if current state satisfies the limit
23            }
24
25            // Reference to the result stored in dp for current state
26            ll &result = dp[remainingZeros][remainingOnes][currentState];
27            if (result != -1) {
28                return result; // If result is already calculated, return it to avoid recomputation
29            }
30
31            // Calculate the result based on current state
32            if (currentState == 0) {
33                // If in state 0 (zero), try transitioning from previous state
34                result = (dfs(dfs, remainingZeros - 1, remainingOnes, 0) +
35                          dfs(dfs, remainingZeros - 1, remainingOnes, 1) -
36                          dfs(dfs, remainingZeros - limit - 1, remainingOnes, 1) + MODULO) % MODULO;
37            } else {
38                // If in state 1 (one), try transitioning from previous state
39                result = (dfs(dfs, remainingZeros, remainingOnes - 1, 0) +
40                          dfs(dfs, remainingZeros, remainingOnes - 1, 1) -
41                          dfs(dfs, remainingZeros, remainingOnes - limit - 1, 0) + MODULO) % MODULO;
42            }
43
44            return result; // Return the calculated result
45        };
46
47        // Compute and return the total number of stable arrays by summing over all initial states
48        return (dfs(dfs, zero, one, 0) + dfs(dfs, zero, one, 1)) % MODULO;
49    }
50};
51

1// Function to calculate the number of stable arrays based on given parameters.
2function numberOfStableArrays(zero: number, one: number, limit: number): number {
3    const MODULO = 1e9 + 7;
4
5    // 3-dimensional array to store intermediate results for memoization.
6    const dp: number[][][] = Array.from({ length: zero + 1 }, () =>
7        Array.from({ length: one + 1 }, () => [-1, -1])
8    );
9
10    // Depth-first search function with memoization.
11    const dfs = (remainingZero: number, remainingOne: number, lastDigit: number): number => {
12        // Base case: if there are more zeros or ones used than allowed, return 0.
13        if (remainingZero < 0 || remainingOne < 0) {
14            return 0;
15        }
16
17        // Base case: if no more zeros are needed, check validity.
18        if (remainingZero === 0) {
19            return lastDigit === 1 && remainingOne <= limit ? 1 : 0;
20        }
21
22        // Base case: if no more ones are needed, check validity.
23        if (remainingOne === 0) {
24            return lastDigit === 0 && remainingZero <= limit ? 1 : 0;
25        }
26
27        // Check if result is already computed and stored in dp table.
28        let result = dp[remainingZero][remainingOne][lastDigit];
29        if (result !== -1) {
30            return result;
31        }
32
33        // Calculate result based on the last used digit.
34        if (lastDigit === 0) {
35            // Compute possibilities starting with 0 as last digit.
36            result = (
37                dfs(remainingZero - 1, remainingOne, 0) +
38                dfs(remainingZero - 1, remainingOne, 1) -
39                dfs(remainingZero - limit - 1, remainingOne, 1) +
40                MODULO
41            ) % MODULO;
42        } else {
43            // Compute possibilities starting with 1 as last digit.
44            result = (
45                dfs(remainingZero, remainingOne - 1, 0) +
46                dfs(remainingZero, remainingOne - 1, 1) -
47                dfs(remainingZero, remainingOne - limit - 1, 0) +
48                MODULO
49            ) % MODULO;
50        }
51
52        // Store the computed result in the dp table.
53        return (dp[remainingZero][remainingOne][lastDigit] = result);
54    };
55
56    // Calculate the total number of stable arrays by starting from both possible last digits (0 and 1).
57    return (dfs(zero, one, 0) + dfs(zero, one, 1)) % MODULO;
58}
59

Time and Space Complexity

The time complexity of the provided numberOfStableArrays function is determined by the recursive depth of the dfs function with caching. The state of the recursive calls is defined by three parameters: i, j, and k. This results in a time complexity of O(zero * one * 2), which simplifies to O(zero * one), since the third parameter k can only be 0 or 1, indicating two possible states for each pair of (i, j).

The space complexity is mainly due to the storage of memoized states in the caching mechanism. The space required to store the results of these states is also O(zero * one * 2), simplifying again to O(zero * one). This represents all combinations of i and j with each value of k.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems