3699. Number of ZigZag Arrays I

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 <= 2000
• 1 <= l < r <= 2000

 

Solutions

Solution: Dynamic Programming + Prefix Sum

• Time complexity: O(nr)
• Space complexity: O(r)

 

JavaScript

/**
 * @param {number} n
 * @param {number} l
 * @param {number} r
 * @return {number}
 */
const zigZagArrays = function (n, l, r) {
  const MODULO = 10 ** 9 + 7;
  const incDp = Array.from({ length: r + 1 }, () => 0);
  const decDp = Array.from({ length: r + 1 }, () => 0);
  const incSum = Array.from({ length: r + 1 }, () => 0);
  const decSum = Array.from({ length: r + 1 }, () => 0);

  for (let index = l; index <= r; index++) {
    const len = index - l + 1;

    incDp[index] = 1;
    decDp[index] = 1;
    incSum[index] = len;
    decSum[index] = len;
  }

  let len = 1;

  while (len < n) {
    for (let index = l; index <= r; index++) {
      incDp[index] = (decSum[r] - decSum[index] + MODULO) % MODULO;
      decDp[index] = incSum[index - 1];
    }

    incSum[l] = incDp[l];
    decSum[l] = decDp[l];

    for (let index = l + 1; index <= r; index++) {
      incSum[index] = (incSum[index - 1] + incDp[index]) % MODULO;
      decSum[index] = (decSum[index - 1] + decDp[index]) % MODULO;
    }

    len += 1;
  }

  return (incSum[r] + decSum[r]) % MODULO;
};