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 <= 20001 <= l < r <= 2000
Solutions
Too much of a complicated question for breakfast.
/**
* @param {number} n
* @param {number} l
* @param {number} r
* @return {number}
*/
var zigZagArrays = function (n, l, r) {
const dp0 = new Array(r + 1).fill(0);
const dp1 = new Array(r + 1).fill(0);
const sum0 = new Array(r + 2).fill(0);
const sum1 = new Array(r + 2).fill(0);
const MOD = 10 ** 9 + 7;
for (let i = l; i <= r; i++) {
dp0[i] = dp1[i] = 1;
sum0[i] = sum1[i] = i - l + 1;
}
for (let i = 1; i < n; i++) {
for (let j = l; j <= r; j++) {
dp0[j] = (sum1[r] - sum1[j] + MOD) % MOD;
dp1[j] = sum0[j - 1];
}
sum0[l] = dp0[l];
sum1[l] = dp1[l];
for (let j = l + 1; j <= r; j++) {
sum0[j] = (sum0[j - 1] + dp0[j]) % MOD;
sum1[j] = (sum1[j - 1] + dp1[j]) % MOD;
}
}
return (sum0[r] + sum1[r]) % MOD;
};