3699. Number of ZigZag Arrays I

Dynamic Programming
Prefix Sum
Combinatorics

TIME

O(n * m) where m = r - l + 1

SPACE

O(m)

Intuition

"No two adjacent equal" plus "no three consecutive strictly monotonic" forces a strict zigzag: the sequence must alternate up, down, up, down (or down, up, down, ...). Only the relative order of values matters, so shift the range [l, r] to 0 .. m-1 where m = r - l + 1; the count depends only on n and m.

We build the sequence one element at a time, tracking the value of the last element and the direction of the last step (since the next step must be the opposite direction).

Approach

Let, for the current length:

up[v] = number of valid zigzag sequences ending at value v whose last step went up (prev < v),
down[v] = number ending at v whose last step went down (prev > v).

Because directions must alternate:

new_up[v]   = sum over u < v of down[u]      (a down step preceded this up step)
new_down[v] = sum over u > v of up[u]         (an up step preceded this down step)

The first sum is a prefix sum of down; the second a suffix sum of up each extension is O(m).

Base (length 1): up[v] = down[v] = 1 for all v.
Repeat the transition n - 1 times.
Answer = sum(up[v] + down[v]) mod (10^9 + 7).

(There is a mirror symmetry down[v] = up[m-1-v], so the total equals 2 * sum(up); both arrays are kept for clarity.)

Complexity

Time: O(n * m), n length steps, each O(m) via prefix/suffix sums
Space: O(m), two rolling arrays

Edge Cases

m = 2 (e.g. l, r adjacent) -> only the two alternating arrays, answer 2
Minimum length n = 3
All arithmetic taken modulo 10^9 + 7
Symmetry halves the conceptual work but the loop already runs in O(n * m)

Code

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        """
        3699. Number of ZigZag Arrays I
        Time: O(n * m) where m = r - l + 1
        Space: O(m)
        """
        MOD = 10**9 + 7
        m = r - l + 1

        # up[v]/down[v]: sequences ending at value v with last step up/down.
        up = [1] * m
        down = [1] * m

        for _ in range(2, n + 1):
            new_up = [0] * m
            new_down = [0] * m

            prefix = 0  # sum of down[u] for u < v
            for v in range(m):
                new_up[v] = prefix
                prefix = (prefix + down[v]) % MOD

            suffix = 0  # sum of up[u] for u > v
            for v in range(m - 1, -1, -1):
                new_down[v] = suffix
                suffix = (suffix + up[v]) % MOD

            up, down = new_up, new_down

        return (sum(up) + sum(down)) % MOD

/**
 * 3699. Number of ZigZag Arrays I
 * Time: O(n * m) where m = r - l + 1
 * Space: O(m)
 */
class Solution {
    private static final int MOD = 1_000_000_007;

    public int zigZagArrays(int n, int l, int r) {
        int m = r - l + 1;

        // up[v]/down[v]: sequences ending at value v with last step up/down.
        long[] up = new long[m];
        long[] down = new long[m];
        for (int v = 0; v < m; v++) {
            up[v] = 1;
            down[v] = 1;
        }

        for (int step = 2; step <= n; step++) {
            long[] newUp = new long[m];
            long[] newDown = new long[m];

            long prefix = 0; // sum of down[u] for u < v
            for (int v = 0; v < m; v++) {
                newUp[v] = prefix;
                prefix = (prefix + down[v]) % MOD;
            }

            long suffix = 0; // sum of up[u] for u > v
            for (int v = m - 1; v >= 0; v--) {
                newDown[v] = suffix;
                suffix = (suffix + up[v]) % MOD;
            }

            up = newUp;
            down = newDown;
        }

        long answer = 0;
        for (int v = 0; v < m; v++) {
            answer = (answer + up[v] + down[v]) % MOD;
        }
        return (int) answer;
    }
}