3700. Number of ZigZag Arrays II Solution

The problem

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 10⁹ + 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 <= 10⁹
1 <= l < r <= 75

Approach overview

Problem Overview: You need to count how many arrays satisfy a zigzag pattern, where adjacent elements strictly alternate between increasing and decreasing. The task is combinatorial in nature, and brute-force generation quickly becomes infeasible as the array length grows.

Approach 1: Brute Force Enumeration (Exponential Time, O(n) Space)

The most direct idea is to generate every possible array and check whether it satisfies the zigzag condition. During generation, compare each adjacent pair and ensure the relationship alternates between < and >. This approach uses recursion or backtracking and keeps track of the previous value and the expected direction. While simple to reason about, the search space grows exponentially with the array length, leading to O(m^n) time complexity and O(n) recursion stack space.

Approach 2: Dynamic Programming with Direction State (O(n * m^2) Time, O(n * m) Space)

A better approach models the problem using dynamic programming. Let dp[i][v][d] represent the number of valid zigzag arrays of length i that end with value v, where d indicates whether the previous step was increasing or decreasing. To transition, iterate through all valid previous values that satisfy the required relation (smaller values for an increasing step, larger values for a decreasing step). This captures the alternating constraint explicitly, but each transition may scan many candidate values, producing O(n * m^2) time.

Approach 3: DP with Prefix Sum Optimization (O(n * m) Time, O(n * m) Space)

The optimized solution removes the inner scan using prefix sums. Instead of iterating over all smaller or larger values, maintain cumulative counts so each transition becomes a constant-time lookup. For example, when computing increasing states, you sum all counts from values smaller than the current value using a prefix array. For decreasing states, use a suffix or reversed prefix sum. This transforms the DP transition into O(1), reducing the total complexity to O(n * m) time and O(n * m) space. The approach combines ideas from math counting techniques and efficient DP transitions.

Recommended for interviews: Start by explaining the brute-force generation to show you understand the zigzag constraint. Then transition to the DP formulation that tracks the last value and direction. Interviewers typically expect the prefix-sum optimized DP because it demonstrates strong command of dynamic programming state design and transition optimization.

Solution

Java

class Solution {
    private static final long MOD = 1_000_000_007L;

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

        long[][] trans = new long[size][size];
        for (int x = 0; x < m; x++) {
            for (int y = 0; y < x; y++) {
                trans[y][m + x] = 1;
            }
        }

        // down[x] -> up[y] where y > x
        for (int x = 0; x < m; x++) {
            for (int y = x + 1; y < m; y++) {
                trans[m + y][x] = 1;
            }
        }

        long[][] power = matrixPow(trans, n - 1);

        long[] init = new long[size];
        for (int i = 0; i < m; i++) {
            init[i] = 1;
            init[m + i] = 1;
        }

        long[] result = multiply(power, init);

        long ans = 0;
        for (long v : result) {
            ans = (ans + v) % MOD;
        }

        return (int) ans;
    }

    private long[] multiply(long[][] mat, long[] vec) {
        int n = mat.length;
        long[] res = new long[n];

        for (int i = 0; i < n; i++) {
            long sum = 0;
            for (int j = 0; j < n; j++) {
                sum = (sum + mat[i][j] * vec[j]) % MOD;
            }
            res[i] = sum;
        }

        return res;
    }

    private long[][] matrixPow(long[][] mat, long exp) {
        int n = mat.length;

        long[][] res = new long[n][n];
        for (int i = 0; i < n; i++) {
            res[i][i] = 1;
        }

        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = multiply(res, mat);
            }

            mat = multiply(mat, mat);
            exp >>= 1;
        }

        return res;
    }

    private long[][] multiply(long[][] a, long[][] b) {
        int n = a.length;
        long[][] res = new long[n][n];

        for (int i = 0; i < n; i++) {
            for (int k = 0; k < n; k++) {
                if (a[i][k] == 0) continue;

                long aik = a[i][k];

                for (int j = 0; j < n; j++) {
                    if (b[k][j] == 0) continue;

                    res[i][j] = (res[i][j] + aik * b[k][j]) % MOD;
                }
            }
        }

        return res;
    }
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Backtracking	O(m^n)	O(n)	Useful for understanding the zigzag constraint or verifying small inputs
Dynamic Programming (State: index, value, direction)	O(n * m^2)	O(n * m)	Good intermediate solution when constraints are moderate
DP with Prefix Sum Optimization	O(n * m)	O(n * m)	Optimal approach for large inputs; eliminates expensive inner loops

Frequently asked questions

Is Number of ZigZag Arrays II easy or hard?

Number of ZigZag Arrays II is categorized as Hard because it requires careful DP state design and optimization. A naive DP leads to O(n * m^2) transitions, and recognizing the prefix sum optimization is the key step to reach the optimal solution.

Number of ZigZag Arrays II Python/Java solution

Implement a DP table where dp[i][v][dir] stores the number of valid arrays of length i ending at value v with direction dir. Maintain prefix sums to compute transitions efficiently. The same logic works in Python, Java, C++, and Go with O(n * m) complexity.

How to solve Number of ZigZag Arrays II in O(n*m)?

Define DP states that track the array length, last value, and the direction of the previous comparison (up or down). Maintain prefix sums of counts for each direction so transitions from smaller or larger values can be computed instantly. This eliminates the inner loop and reduces the complexity to O(n * m).

What is the best approach for Number of ZigZag Arrays II?

The most efficient approach uses dynamic programming with prefix sum optimization. The DP tracks the last value and whether the previous step was increasing or decreasing. Prefix sums allow transitions from smaller or larger values in constant time, giving O(n * m) time complexity and O(n * m) space.

Is Number of ZigZag Arrays II asked at Google/Amazon/Meta?

Zigzag and alternating sequence problems frequently appear in interviews at companies like Google, Amazon, and Meta because they test dynamic programming state design and combinatorial reasoning. Variants of alternating array counting and wiggle sequence problems are common interview topics.

What data structure is used in Number of ZigZag Arrays II?

The main structure is a dynamic programming table that stores counts for each length, ending value, and direction state. Prefix sum arrays are used to accelerate transitions by quickly aggregating counts of smaller or larger values.

What is the time complexity of Number of ZigZag Arrays II?

The optimized dynamic programming solution runs in O(n * m) time, where n is the array length and m is the range of possible values. Each DP state is computed using prefix sums instead of scanning all candidates, reducing the transition cost to O(1). Space complexity is O(n * m).

Number of ZigZag Arrays II solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Number of ZigZag Arrays II solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems