3130. Find All Possible Stable Binary Arrays II

Description

You are given 3 positive integers zero, one, and limit.

A 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 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].

Example 2:

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

Output: 1

Explanation:

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

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

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(zero*one)
• Space complexity: O(zero*one)

 

JavaScript

/**
 * @param {number} zero
 * @param {number} one
 * @param {number} limit
 * @return {number}
 */
const numberOfStableArrays = function (zero, one, limit) {
  const MODULO = 10 ** 9 + 7;
  const dp = Array.from({ length: zero + 1 }, () => {
    return new Array(one + 1).fill('').map(() => new Array(2).fill(-1));
  });

  const getStableCount = (zeros, ones, last) => {
    if (zeros === 0) {
      return last === 0 || ones > limit ? 0 : 1;
    }

    if (ones === 0) {
      return last === 1 || zeros > limit ? 0 : 1;
    }

    if (dp[zeros][ones][last] !== -1) {
      return dp[zeros][ones][last];
    }

    let result = 0;

    if (last === 0) {
      const lastZeroCount = getStableCount(zeros - 1, ones, 0);
      const lastOneCount = getStableCount(zeros - 1, ones, 1);

      result = (lastZeroCount + lastOneCount) % MODULO;

      if (zeros > limit) {
        const raceCount = getStableCount(zeros - limit - 1, ones, 1);

        result = (result - raceCount + MODULO) % MODULO;
      }
    } else {
      const lastZeroCount = getStableCount(zeros, ones - 1, 0);
      const lastOneCount = getStableCount(zeros, ones - 1, 1);

      result = (lastZeroCount + lastOneCount) % MODULO;

      if (ones > limit) {
        const raceCount = getStableCount(zeros, ones - limit - 1, 0);

        result = (result - raceCount + MODULO) % MODULO;
      }
    }

    dp[zeros][ones][last] = result;

    return result;
  };

  const lastZeroCount = getStableCount(zero, one, 0);
  const lastOneCount = getStableCount(zero, one, 1);

  return (lastZeroCount + lastOneCount) % MODULO;
};