Scale Engineer

Find All Possible Stable Binary Arrays I

Med
#2779Time: O(zero * one * limit). We have nested loops for `i` (up to `zero`), `j` (up to `one`), and an inner summation loop `k` (up to `limit`).Space: O(zero * one). We use a 3D DP table of size `(zero + 1) x (one + 1) x 2`.
Patterns
Dynamic ProgrammingPrefix Sum

Prompt

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 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], as both arrays have a single 0 and a single 1, and no subarray has a length greater than 2.

Example 2:

Input: zero = 1, one = 2, limit = 1

Output: 1

Explanation:

The only possible stable binary array is [1,0,1].

Note that the binary arrays [1,1,0] and [0,1,1] have subarrays of length 2 with identical elements, hence, they are not stable.

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

Approaches

2 approaches with complexity analysis and trade-offs.

This problem can be solved using dynamic programming. We build the stable arrays by adding one element at a time, keeping track of the number of zeros and ones used, and what the last element was. This helps us enforce the limit constraint on consecutive identical elements.

Algorithm

  • Let dp[i][j][0] be the number of stable binary arrays using i zeros and j ones that end with a '0'.
  • Let dp[i][j][1] be the number of stable binary arrays using i zeros and j ones that end with a '1'.
  • The state transitions are based on the idea that an array ending in a block of k identical elements must have been formed by appending that block to an array ending in the opposite element.
  • Transition for dp[i][j][0]: An array with i zeros and j ones ending in '0' must be formed by appending a block of k zeros (where 1 <= k <= limit) to a valid array with i-k zeros and j ones that ends in '1'. dp[i][j][0] = sum(dp[i-k][j][1] for k in 1..min(i, limit))
  • Transition for dp[i][j][1]: Similarly, an array with i zeros and j ones ending in '1' is formed by appending a block of k ones (1 <= k <= limit) to a valid array with i zeros and j-k ones that ends in '0'. dp[i][j][1] = sum(dp[i][j-k][0] for k in 1..min(j, limit))
  • Base Cases: A block of k zeros can be a valid starting array, so dp[k][0][0] = 1 for 1 <= k <= limit. Similarly, dp[0][k][1] = 1 for 1 <= k <= limit.
  • Algorithm Steps:
    1. Initialize a 3D DP table dp[zero+1][one+1][2] with zeros.
    2. Set the base cases: dp[k][0][0] = 1 for 1 <= k <= limit and dp[0][k][1] = 1 for 1 <= k <= limit.
    3. Iterate i from 1 to zero and j from 1 to one.
    4. Inside the loops, calculate dp[i][j][0] and dp[i][j][1] using the transition formulas, which involve an inner loop up to limit. Remember to take modulo 10^9 + 7 at each addition.
    5. The final answer is (dp[zero][one][0] + dp[zero][one][1]) % MOD.

Walkthrough

A straightforward dynamic programming approach involves defining a state that captures the necessary information to build a valid array. The state should include the number of zeros used, the number of ones used, and the last element added to the array.

Let dp[i][j][0] be the number of stable binary arrays using i zeros and j ones that end with a '0'. Let dp[i][j][1] be the number of stable binary arrays using i zeros and j ones that end with a '1'.

To compute dp[i][j][0], we consider how such an array could be formed. It must end with a block of k zeros, where 1 <= k <= limit. This block must be appended to a valid array of i-k zeros and j ones that ends with a '1'. Thus, we sum up the possibilities over all valid k.

dp[i][j][0] = (dp[i-1][j][1] + dp[i-2][j][1] + ... + dp[i-min(i, limit)][j][1]) % MOD

Similarly, for dp[i][j][1]:

dp[i][j][1] = (dp[i][j-1][0] + dp[i][j-2][0] + ... + dp[i][j-min(j, limit)][0]) % MOD

The base cases are arrays that consist of only one type of element. An array of k zeros (with 1 <= k <= limit) is a valid base case, as is an array of k ones.

We can then fill the DP table iteratively. The final answer is the sum of ways to form an array with zero zeros and one ones, ending in either '0' or '1'.

class Solution {    public int numberOfStableArrays(int zero, int one, int limit) {        int MOD = 1_000_000_007;        long[][][] dp = new long[zero + 1][one + 1][2];         // Base cases: arrays consisting of only 0s or only 1s        for (int i = 1; i <= Math.min(zero, limit); i++) {            dp[i][0][0] = 1;        }        for (int j = 1; j <= Math.min(one, limit); j++) {            dp[0][j][1] = 1;        }         for (int i = 1; i <= zero; i++) {            for (int j = 1; j <= one; j++) {                // Calculate dp[i][j][0]: ends with 0                // This is formed by appending k zeros to an array ending in 1.                // Sum up dp[i-k][j][1] for k from 1 to limit.                for (int k = 1; k <= Math.min(i, limit); k++) {                    dp[i][j][0] = (dp[i][j][0] + dp[i - k][j][1]) % MOD;                }                 // Calculate dp[i][j][1]: ends with 1                // This is formed by appending k ones to an array ending in 0.                // Sum up dp[i][j-k][0] for k from 1 to limit.                for (int k = 1; k <= Math.min(j, limit); k++) {                    dp[i][j][1] = (dp[i][j][1] + dp[i][j - k][0]) % MOD;                }            }        }         return (int) ((dp[zero][one][0] + dp[zero][one][1]) % MOD);    }}

Complexity

Time

O(zero * one * limit). We have nested loops for `i` (up to `zero`), `j` (up to `one`), and an inner summation loop `k` (up to `limit`).

Space

O(zero * one). We use a 3D DP table of size `(zero + 1) x (one + 1) x 2`.

Trade-offs

Pros

  • Relatively straightforward to conceptualize from the problem definition.

Cons

  • The time complexity might be too high for larger constraints, although it might pass for the given constraints.

Solutions

class Solution {private  final int mod = (int)1 e9 + 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];  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem