3699. Number of ZigZag Arrays I

Problem Overview

Count zigzag arrays of length n with values in [l, r]: adjacent elements differ, and no three consecutive elements are strictly increasing or decreasing.

Intuition

Count zigzag arrays of length n with values in [l, r]: adjacent elements differ, and no three consecutive elements are strictly increasing or decreasing. Track the last value and whether the previous step went up or down. If the last step was up, the next value must be smaller (otherwise a < b < c). If the last step was down, the next must be larger. Prefix and suffix sums over values make each extension O(r − l).

Algorithm

1Initialize up[v] and down[v] from all length-2 pairs (a, b) with a ≠ b.
2up[b] counts arrays ending at b with a < b; down[b] counts a > b.
3For each additional position: nextUp[w] = sum of down[v] for v < w (prefix).
4nextDown[w] = sum of up[v] for v > w (suffix).
5Repeat for n − 2 extension steps.
6Return sum of up[v] + down[v] over v ∈ [l, r], modulo 10⁹ + 7.

Example Walkthrough

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

1.Length-2 pairs: (4,5) and (5,4) only.
2.From (5, up): next value must be < 5 → 4 gives [4,5,4].
3.From (4, down): next value must be > 4 → 5 gives [5,4,5].
4.Total = 2.

Output: 2

Common Pitfalls

•From “last step up” only allow w < v — not w > v (creates strictly increasing triple).
•Use long for DP counts before the final modulo.
•Initialize with pairs at length 2, then loop n − 2 times (not n − 1).

3699.cs

// Approach: DP on (last value, last step direction). After placing the first two distinct values,
// state (v, up) means the last element is v and the previous element is smaller; (v, down) means larger.
// To extend: from (v, up) only add w < v (blocks a<b<c); from (v, down) only add w > v (blocks a>b>c).
// Use prefix/suffix sums over values to transition in O(r - l) per length instead of O(V^2).
// Time: O(n * (r - l)) Space: O(r - l)
public class Solution
{
    private const int Mod = 1_000_000_007;

    public int ZigZagArrays(int n, int l, int r)
    {
        long[] up = new long[r + 1];
        long[] down = new long[r + 1];

        for (int a = l; a <= r; a++)
        {
            for (int b = l; b <= r; b++)
            {
                if (a == b) 
                    continue;
                if (a < b) 
                    up[b] = (up[b] + 1) % Mod;
                else 
                    down[b] = (down[b] + 1) % Mod;
            }
        }

        for (int len = 2; len < n; len++)
        {
            long[] nextUp = new long[r + 1];
            long[] nextDown = new long[r + 1];

            long prefixDown = 0;
            for (int w = l; w <= r; w++)
            {
                nextUp[w] = prefixDown;
                prefixDown = (prefixDown + down[w]) % Mod;
            }

            long suffixUp = 0;
            for (int w = r; w >= l; w--)
            {
                nextDown[w] = suffixUp;
                suffixUp = (suffixUp + up[w]) % Mod;
            }

            up = nextUp;
            down = nextDown;
        }

        long ans = 0;
        for (int v = l; v <= r; v++)
            ans = (ans + up[v] + down[v]) % Mod;

        return (int)ans;
    }
}

Was this solution helpful?