3700. Number of ZigZag Arrays II

Description

You are given three integers n, l, and r.

A ZigZag array of length n is defined as follows:

• Each element lies in the range [l, r].
• No two adjacent elements are equal.
• No three consecutive elements form a strictly increasing or strictly decreasing sequence.

Return the total number of valid ZigZag arrays.

Since the answer may be large, return it modulo 109 + 7.

A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if exists).

A sequence is said to be strictly decreasing if each element is strictly smaller than its previous one (if exists).

 

Example 1:

Input: n = 3, l = 4, r = 5

Output: 2

Explanation:

There are only 2 valid ZigZag arrays of length n = 3 using values in the range [4, 5]:

• [4, 5, 4]
• [5, 4, 5]

Example 2:

Input: n = 3, l = 1, r = 3

Output: 10

Explanation:

​​​​​​​There are 10 valid ZigZag arrays of length n = 3 using values in the range [1, 3]:

• [1, 2, 1], [1, 3, 1], [1, 3, 2]
• [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2]
• [3, 1, 2], [3, 1, 3], [3, 2, 3]

All arrays meet the ZigZag conditions.

 

Constraints:

• 3 <= n <= 109
• 1 <= l < r <= 75​​​​​​​

 

Solutions

Solution: Dynamic Programming

• Time complexity: O(m³logn)
• Space complexity: O(m)

 

JavaScript

/**
 * @param {number} n
 * @param {number} l
 * @param {number} r
 * @return {number}
 */
const zigZagArrays = function (n, l, r) {
  const m = r - l + 1;

  if (n === 1) return m;

  const MODULO = BigInt(10 ** 9 + 7);
  let matrix = Array.from({ length: m }, (_, a) => {
    return Array.from({ length: m }, (_, b) => (a + b + 1 < m ? 1n : 0n));
  });
  let result = Array.from({ length: m }, () => 1n);
  let count = n - 1;

  while (count) {
    if (count % 2) {
      result = multiplyVectorMatrix(result, matrix, MODULO);
    }

    matrix = multiplyMatrixMatrix(matrix, matrix, MODULO);
    count = Math.floor(count / 2);
  }

  const sum = result.reduce((total, count) => total + count);

  return Number((sum * 2n) % MODULO);
};

function multiplyVectorMatrix(vector, matrix, mod) {
  const n = vector.length;
  const result = new Array(n).fill(0n);

  for (let a = 0; a < n; a++) {
    for (let b = 0; b < n; b++) {
      result[a] += vector[b] * matrix[a][b];
    }

    result[a] %= mod;
  }

  return result;
}

function multiplyMatrixMatrix(matA, matB, mod) {
  const m = matA.length;
  const n = matA[0].length;
  const p = matB[0].length;
  const result = Array.from({ length: m }, () => new Array(n).fill(0n));

  for (let a = 0; a < m; a++) {
    for (let b = 0; b < p; b++) {
      for (let c = 0; c < n; c++) {
        result[a][b] += matA[a][c] * matB[c][b];
      }

      result[a][b] %= mod;
    }
  }

  return result;
}