3130. Find All Possible Stable Binary Arrays II

Problem Description

You are given three positive integers: zero, one, and limit.

A binary array arr is considered 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 result can be very large, return it modulo (10^9 + 7).

Intuition

To solve the problem, we need to design a function that calculates the number of ways to form stable binary arrays given the constraints. Here's a step-by-step breakdown:

Conceptualizing the Recursion: We can use a recursive approach where:
- We define a function dfs(i, j, k) where i is the number of 0's left to place, j is the number of 1's left to place, and k is the next number to be added (either 0 or 1).
Basic Cases:
- If all 0's (i = 0) are placed, return 1 if k = 1 and there are no more than limit 1's left (j <= limit), otherwise return 0.
- If all 1's (j = 0) are placed, similarly return 1 if k = 0 and there are no more than limit 0's left (i <= limit), otherwise return 0.
Recursive Cases:
- If k = 0 (next to place is 0), evaluate adding a 0 (dfs(i - 1, j, 0)) and adding a 1 (dfs(i - 1, j, 1)), subtract scenarios that break the limit rule.
- If k = 1, similarly, evaluate both possibilities and adjust for breaking the limit on consecutive 1's.
Combining Results: Compute results starting with both 0 and 1 (dfs(zero, one, 0) and dfs(zero, one, 1)) and take their sum.
Modulo Operation: Since numbers might be large, we take the result modulo (10^9 + 7).

The recursive function efficiently counts valid configurations by exploring all possibilities while tracking placements and ensuring stability constraints.

Learn more about Dynamic Programming and Prefix Sum patterns.

Solution Approach

The solution utilizes memoization search to efficiently calculate the number of stable binary arrays. Here’s a detailed breakdown of the approach:

Memoization with Recursion:
- We use a recursive depth-first search (dfs) with memoization to avoid recalculating solutions for subproblems.
- The function dfs(i, j, k) is defined where i is the number of 0's left, j is the number of 1's left, and k is the next number to be placed (either 0 or 1).
Handling Base Cases:
- If all 0's are placed (i == 0), return 1 when the next number is 1 (k = 1) and the count of remaining 1's is within the limit (j <= limit), otherwise return 0.
- If all 1's are placed (j == 0), return 1 when the next number is 0 (k = 0) and remaining 0's fit within the limit (i <= limit), otherwise, return 0.
Recursive Transition:
- When adding a 0 (k = 0):
  - Explore the option where the last added number was also 0 (dfs(i - 1, j, 0)).
  - Explore the option where the last added number was 1 (dfs(i - 1, j, 1)).
  - Subtract the scenario where a subarray of more than limit 0's might have been formed, ensuring stable constraints are met.
- When adding a 1 (k = 1):
  - Explore continuation with a 1 (dfs(i, j - 1, 1)) and switch to a 0 (dfs(i, j - 1, 0)).
  - Similarly, deduct cases that could result in unstable arrays longer than limit consisting of only 1's.
Modular Arithmetic:
- Once calculations are done, use a modulo operation (10^9 + 7) to prevent overflow issues.
Final Calculation:
- The results are gathered by initiating both a 0 and a 1 as the first element, summing the counts from dfs(zero, one, 0) and dfs(zero, one, 1) to get the final answer.
- Clear the cache to manage memory effectively.

These steps ensure that the solution efficiently computes the desired result by iterating over possible configurations while leveraging memoization for optimal performance.

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 the following small example:

zero = 2: We need exactly two 0's in the binary array.
one = 2: We need exactly two 1's in the binary array.
limit = 2: Every subarray larger than this limit must contain both 0 and 1.

With these values, the goal is to determine how many binary arrays we can create while following the stability constraints.

Steps to Formulate Arrays

Initialize with Recursion:
- Start the recursive exploration with the possibility of the first number being either a 0 or a 1. Thus, we look at dfs(2, 2, 0) and dfs(2, 2, 1).
Recursive Exploration (Example):
- Assume we start with dfs(2, 2, 0) (first number as 0).
Base Cases:
- If placing a 0, it reduces our requirement, so move to dfs(1, 2, 0) or dfs(1, 2, 1).
- If placing a 1 at this step, consider dfs(2, 1, 0) and dfs(2, 1, 1).
Continuing Depth:
- Follow through until dfs(0, 2, k) where k could be 0 or 1. If k = 1 and remaining 1’s ≤ limit, return 1. Similarly, compute for other combinations.
Handling Constraints:
- Ensure no subarray longer than limit consists only of 0's or 1's. If identified, subtract these scenarios from the valid count.
Combine Results:
- Calculate viable binary arrays starting 0 by dfs(2, 2, 0) and starting 1 by dfs(2, 2, 1). Sum the valid scenarios.
Final Computation:
- Results from all recursive paths are aggregated, and since answers might be large, return it modulo (10^9 + 7).

The complete process leverages memoization to optimize repeated calculations, ensuring efficient evaluation of all potential configurations while adhering to the constraints of number placements and subarray criteria. This approach finds stable binary arrays for the example provided.

Solution Implementation

1from functools import cache
2
3class Solution:
4    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
5        # Use a cache to memoize results of the recursive function
6        @cache
7        def dfs(num_zeros: int, num_ones: int, is_last_one: int) -> int:
8            # If no zeros left, check if the number of ones is within the limit
9            if num_zeros == 0:
10                return int(is_last_one == 1 and num_ones <= limit)
11
12            # If no ones left, check if the number of zeros is within the limit
13            if num_ones == 0:
14                return int(is_last_one == 0 and num_zeros <= limit)
15
16            if is_last_one == 0:
17                # Branch where last element is zero:
18                # Include a sequence ending in a zero, and consider both options for next element
19                result = dfs(num_zeros - 1, num_ones, 0) + dfs(num_zeros - 1, num_ones, 1)
20                # Adjust for overcounting by subtracting paths that have more zeros than allowed by limit
21                if num_zeros - limit - 1 >= 0:
22                    result -= dfs(num_zeros - limit - 1, num_ones, 1)
23                return result
24            else:
25                # Branch where last element is one:
26                # Include a sequence ending in a one, and consider both options for next element
27                result = dfs(num_zeros, num_ones - 1, 0) + dfs(num_zeros, num_ones - 1, 1)
28                # Adjust for overcounting by subtracting paths that have more ones than allowed by limit
29                if num_ones - limit - 1 >= 0:
30                    result -= dfs(num_zeros, num_ones - limit - 1, 0)
31                return result
32
33        # Calculate the total number of stable arrays, considering both starting with zero and one
34        mod = 10**9 + 7
35        answer = (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
36
37        # Clear the cache to free memory
38        dfs.cache_clear()
39
40        return answer
41

1class Solution {
2    // Define a constant for the modulus operation
3    private final int MOD = (int) 1e9 + 7;
4  
5    // 3D array for memoization
6    private Long[][][] memo;
7  
8    // Limit for consecutive elements
9    private int limit;
10  
11    public int numberOfStableArrays(int zero, int one, int limit) {
12        // Initialize memoization array with dimensions based on `zero` and `one`
13        memo = new Long[zero + 1][one + 1][2];
14        this.limit = limit; // Set the limit
15        // Start the DFS from both 0 and 1 as starting elements and sum the results
16        return (int) ((dfs(zero, one, 0) + dfs(zero, one, 1)) % MOD);
17    }
18
19    private long dfs(int countZero, int countOne, int lastElement) {
20        // If either count of zeroes or ones becomes negative, return 0 as it is an invalid state
21        if (countZero < 0 || countOne < 0) {
22            return 0;
23        }
24      
25        // If there are no more zeroes to place
26        if (countZero == 0) {
27            // Return 1 if last placed was 1 and count of `one` is within limit
28            return (lastElement == 1 && countOne <= limit) ? 1 : 0;
29        }
30      
31        // If there are no more ones to place
32        if (countOne == 0) {
33            // Return 1 if last placed was 0 and count of `zero` is within limit
34            return (lastElement == 0 && countZero <= limit) ? 1 : 0;
35        }
36      
37        // If already computed, return memoized value
38        if (memo[countZero][countOne][lastElement] != null) {
39            return memo[countZero][countOne][lastElement];
40        }
41      
42        // If last element is 0, add possible outcomes of placing the next 0 or 1
43        if (lastElement == 0) {
44            memo[countZero][countOne][lastElement] = 
45                (dfs(countZero - 1, countOne, 0) + dfs(countZero - 1, countOne, 1) 
46                - dfs(countZero - limit - 1, countOne, 1) + MOD) % MOD;
47        } 
48        // If last element is 1, add possible outcomes of placing the next 0 or 1
49        else {
50            memo[countZero][countOne][lastElement] = 
51                (dfs(countZero, countOne - 1, 0) + dfs(countZero, countOne - 1, 1) 
52                - dfs(countZero, countOne - limit - 1, 0) + MOD) % MOD;
53        }
54      
55        // Return the computed value
56        return memo[countZero][countOne][lastElement];
57    }
58}
59

1class Solution {
2public:
3    // Function to calculate the number of stable arrays.
4    int numberOfStableArrays(int zero, int one, int limit) {
5        const int mod = 1e9 + 7; // Modulo value for result to prevent overflow.
6        using ll = long long; // Define a shorthand for long long int.
7      
8        // Create a 3D vector to store intermediate results for memoization.
9        std::vector<std::vector<std::array<ll, 2>>> f(zero + 1, std::vector<std::array<ll, 2>>(one + 1, {-1, -1}));
10      
11        // Define a lambda function for the depth-first search with memoization.
12        auto dfs = [&](auto&& dfs, int i, int j, int k) -> ll {
13            // Base case: if the number of zeroes or ones is negative, return 0.
14            if (i < 0 || j < 0) {
15                return 0;
16            }
17            // Base case: if no zeroes are left, check if a stable arrangement with ones is possible.
18            if (i == 0) {
19                return k == 1 && j <= limit;
20            }
21            // Base case: if no ones are left, check if a stable arrangement with zeroes is possible.
22            if (j == 0) {
23                return k == 0 && i <= limit;
24            }
25          
26            ll& res = f[i][j][k]; // Reference to the memoized result.
27          
28            // If a result has already been computed, return it.
29            if (res != -1) {
30                return res;
31            }
32          
33            // If k is 0, the last used was a 'zero'. Calculate the number of ways for this condition.
34            if (k == 0) {
35                res = (dfs(dfs, i - 1, j, 0) + dfs(dfs, i - 1, j, 1) - dfs(dfs, i - limit - 1, j, 1) + mod) % mod;
36            } else { // If k is 1, the last used was a 'one'. Calculate the number of ways for this condition.
37                res = (dfs(dfs, i, j - 1, 0) + dfs(dfs, i, j - 1, 1) - dfs(dfs, i, j - limit - 1, 0) + mod) % mod;
38            }
39          
40            // Return the computed result.
41            return res;
42        };
43      
44        // Sum the results for both possible last elements ('zero' or 'one') and return modulo 'mod'.
45        return (dfs(dfs, zero, one, 0) + dfs(dfs, zero, one, 1)) % mod;
46    }
47};
48

1// Modulo value to prevent overflow.
2const MOD = 1e9 + 7;
3
4// Cache for memoization. 
5let memo: number[][][];
6
7// Function to calculate the number of stable arrays.
8function numberOfStableArrays(zero: number, one: number, limit: number): number {
9    // Initialize the memoization cache with dimensions (zero + 1) x (one + 1) x 2, filled with -1.
10    memo = Array.from({ length: zero + 1 }, () =>
11        Array.from({ length: one + 1 }, () =>
12            Array(2).fill(-1)
13        )
14    );
15
16    // Inner recursive function for depth-first search with memoization.
17    function dfs(i: number, j: number, k: number): number {
18        // If negative counts are encountered, the configuration is invalid.
19        if (i < 0 || j < 0) {
20            return 0;
21        }
22
23        // If there are no zeroes left, check if a stable arrangement of ones is possible.
24        if (i === 0) {
25            return (k === 1 && j <= limit) ? 1 : 0;
26        }
27
28        // If there are no ones left, check if a stable arrangement of zeroes is possible.
29        if (j === 0) {
30            return (k === 0 && i <= limit) ? 1 : 0;
31        }
32
33        // Reference to the memoized result.
34        let res = memo[i][j][k];
35
36        // If a result has been previously computed, return it.
37        if (res !== -1) {
38            return res;
39        }
40
41        if (k === 0) { // If the last element was a 'zero'.
42            res = (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - dfs(i - limit - 1, j, 1) + MOD) % MOD;
43        } else { // If the last element was a 'one'.
44            res = (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - dfs(i, j - limit - 1, 0) + MOD) % MOD;
45        }
46
47        // Store the computed result in the memoization cache.
48        memo[i][j][k] = res;
49
50        return res;
51    }
52
53    // Compute the total ways by summing results for both last element scenarios: 'zero' or 'one'.
54    return (dfs(zero, one, 0) + dfs(zero, one, 1)) % MOD;
55}
56

Time and Space Complexity

The given code implements a depth-first search (DFS) algorithm with memoization (using @cache) to calculate the number of stable arrays under certain constraints.

Time Complexity

The time complexity of the dfs function is determined by the number of distinct states it explores. Here, the state is represented by the triplet (i, j, k), where:

i can take values from 0 to zero,
j can take values from 0 to one, and
k can take values from 0 to 1.

Thus, the total number of states is O(zero * one * 2). For each state, the function potentially makes constant time recursive calls and subtractions. Therefore, the overall time complexity is O(zero * one).

Space Complexity

The space complexity is driven by two main factors:

Memoization Storage:
- The dfs function caches results for each state (i, j, k), resulting in a cache size of O(zero * one * 2).
Recursion Stack:
- The maximum depth of the recursion stack is O(zero + one), since in the worst case, you might traverse through i + j recursive calls.

Thus, the overall space complexity is O(zero * one + zero + one), which simplifies to O(zero * one).

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

Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.

Which of the following method should we use to solve this problem?

Topological Sort

Uniform Cost Search

Monotonic Stack

Memoization

I don’t know