Number of ZigZag Arrays I
Problem
Given integers n, l, r, count the length-n arrays whose every element is in [l, r], where no two adjacent elements are equal and no three consecutive elements are strictly increasing or strictly decreasing. In other words, the array must strictly alternate up, down, up, down… (a zigzag). Return the count modulo 109 + 7.
n = 3, l = 4, r = 52[4, 5, 4] and [5, 4, 5] zigzag within values {4, 5}.def zigZagArrays(n, l, r):
MOD = 10**9 + 7
m = r - l + 1 # number of distinct values
up = [1] * m # ends at x, next move must be UP
down = [1] * m # ends at x, next move must be DOWN
for _ in range(n - 1): # extend the array one cell at a time
new_up = [0] * m
new_down = [0] * m
prefix = 0 # running sum of up[0..y-1]
for y in range(m): # append y going UP (x < y, from up)
new_down[y] = prefix # next move flips to DOWN
prefix = (prefix + up[y]) % MOD
suffix = 0 # running sum of down[y+1..]
for y in range(m - 1, -1, -1): # append y going DOWN (x > y, from down)
new_up[y] = suffix # next move flips to UP
suffix = (suffix + down[y]) % MOD
up, down = new_up, new_down
return (sum(up) + sum(down)) % MOD # last move was down + last move was upfunction zigZagArrays(n, l, r) {
const MOD = 1000000007n;
const m = r - l + 1; // number of distinct values
let up = new Array(m).fill(1n); // ends at x, next move must be UP
let down = new Array(m).fill(1n); // ends at x, next move must be DOWN
for (let step = 0; step < n - 1; step++) { // extend the array one cell
const nu = new Array(m).fill(0n), nd = new Array(m).fill(0n);
let prefix = 0n; // running sum of up[0..y-1]
for (let y = 0; y < m; y++) { // append y going UP (x < y)
nd[y] = prefix; // next move flips to DOWN
prefix = (prefix + up[y]) % MOD;
}
let suffix = 0n; // running sum of down[y+1..]
for (let y = m - 1; y >= 0; y--) { // append y going DOWN (x > y)
nu[y] = suffix; // next move flips to UP
suffix = (suffix + down[y]) % MOD;
}
up = nu; down = nd;
}
let ans = 0n;
for (let y = 0; y < m; y++) ans = (ans + up[y] + down[y]) % MOD;
return Number(ans);
}int zigZagArrays(int n, int l, int r) {
final long MOD = 1_000_000_007L;
int m = r - l + 1; // number of distinct values
long[] up = new long[m], down = new long[m];
java.util.Arrays.fill(up, 1L); // next move must be UP
java.util.Arrays.fill(down, 1L); // next move must be DOWN
for (int step = 0; step < n - 1; step++) { // extend the array one cell
long[] nu = new long[m], nd = new long[m];
long prefix = 0; // running sum of up[0..y-1]
for (int y = 0; y < m; y++) { // append y going UP (x < y)
nd[y] = prefix; // next move flips to DOWN
prefix = (prefix + up[y]) % MOD;
}
long suffix = 0; // running sum of down[y+1..]
for (int y = m - 1; y >= 0; y--) { // append y going DOWN (x > y)
nu[y] = suffix; // next move flips to UP
suffix = (suffix + down[y]) % MOD;
}
up = nu; down = nd;
}
long ans = 0;
for (int y = 0; y < m; y++) ans = (ans + up[y] + down[y]) % MOD;
return (int) ans;
}int zigZagArrays(int n, int l, int r) {
const long long MOD = 1000000007LL;
int m = r - l + 1; // number of distinct values
vector<long long> up(m, 1), down(m, 1); // next move UP / next move DOWN
for (int step = 0; step < n - 1; step++) { // extend the array one cell
vector<long long> nu(m, 0), nd(m, 0);
long long prefix = 0; // running sum of up[0..y-1]
for (int y = 0; y < m; y++) { // append y going UP (x < y)
nd[y] = prefix; // next move flips to DOWN
prefix = (prefix + up[y]) % MOD;
}
long long suffix = 0; // running sum of down[y+1..]
for (int y = m - 1; y >= 0; y--) { // append y going DOWN (x > y)
nu[y] = suffix; // next move flips to UP
suffix = (suffix + down[y]) % MOD;
}
up = nu; down = nd;
}
long long ans = 0;
for (int y = 0; y < m; y++) ans = (ans + up[y] + down[y]) % MOD;
return (int) ans;
}Explanation
A valid array is a zigzag: consecutive moves strictly alternate between going up and going down. Banning equal neighbours and any three-in-a-row monotone run forces exactly this shape. So building the array left to right, the very next move is fully determined by the previous move — if we just went up we must go down, and vice versa.
That gives a clean DP keyed by the required next direction. Let up[x] be the number of valid prefixes that currently end at value x and whose next move must be up; let down[x] be the same but whose next move must be down. For length 1 every value can later go either way, so both tables start at all 1s.
To extend by one cell to a new value y: appending y as an up step means it came from some up[x] with x < y, and afterwards the next move flips to down. So new_down[y] = ∑x < y up[x]. Symmetrically a down step comes from down[x] with x > y and flips to up: new_up[y] = ∑x > y down[x].
The naive sums are O(m²) per layer. The fix is prefix sums: sweep y left to right keeping a running prefix of up so each new_down[y] is read in O(1); sweep right to left with a running suffix of down for each new_up[y]. Every layer is now O(m), and we do n−1 layers.
After n−1 extensions, each finished array of length n ended with a definite last move: those ending on a down step sit in up, those ending on an up step sit in down. Summing both tables (mod 109+7) counts every zigzag array exactly once. For n = 3, l = 4, r = 5 this returns 2, and for n = 3, l = 1, r = 3 it returns 10.