LeetCode 3699 - Number of ZigZag Arrays I

Difficulty: 🔴 Hard
Topics: Dynamic Programming, Prefix Sum

Solution

Here is the complete technical solution guide for LeetCode 3699 - Number of ZigZag Arrays I, formatted exactly according to your specifications.

Problem Understanding

The problem asks us to count arrays of length n where each element is within the range [l, r] and satisfies the ZigZag constraints. A ZigZag array has two main rules: no two consecutive elements are equal, and no three consecutive elements are strictly increasing or strictly decreasing. The task is to compute the number of valid arrays modulo 10^9 + 7.

The inputs are three integers: n is the length of the array, l and r define the inclusive range of possible values. The output is a single integer representing the total number of arrays meeting the conditions.

Constraints indicate n can be up to 2000 and l and r can also be up to 2000. This means a brute-force enumeration of all sequences is infeasible due to the potentially enormous number of sequences (r - l + 1)^n.

Important edge cases include arrays where r - l is small (which limits the number of distinct values and can trigger repeated elements) and arrays with minimum length n = 3 (the smallest size where the ZigZag conditions on three consecutive elements matter). The problem guarantees n >= 3 and l < r, so we never have zero-length arrays or invalid ranges.

Approaches

Brute Force: The naive approach generates all possible sequences of length n from values [l, r]. For each candidate array, we check the ZigZag conditions by iterating through elements. If any two consecutive elements are equal or any three consecutive elements are strictly increasing or decreasing, we discard it. This approach is correct but computationally infeasible because the total number of sequences is (r - l + 1)^n. For n = 2000 and r - l + 1 ≈ 2000, this is astronomically large.

Optimal Approach: The key observation is that the ZigZag property is local: each element only depends on the previous two elements. This suggests a dynamic programming solution where the state represents the last two chosen elements. Let dp[i][a][b] represent the number of ZigZag arrays of length i ending with elements a and b. We can then compute dp[i+1][b][c] by iterating over all valid c values, ensuring c != b and that a, b, c do not form a strictly increasing or decreasing triplet.

To optimize further, since l <= a, b, c <= r and the DP transition involves summing over all possible next elements, we can use prefix sums to reduce the transition from O(m) per state to O(1) per state. This gives an O(n * m²) solution using prefix sums, which is acceptable given the constraints.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O((r-l+1)^n)	O(n)	Generate all sequences and filter valid ones
Optimal DP with Prefix Sum	O(n * m²)	O(m²)	`m = r-l+1`, uses DP over last two elements with prefix sum optimization

Algorithm Walkthrough

Map the values from [l, r] to [0, m-1] for convenience where m = r - l + 1.
Initialize a 2D DP table dp_prev[a][b] representing the number of ZigZag arrays of length 2 ending with elements a and b. Set dp_prev[a][b] = 1 if a != b.
Iterate from position 3 to n:
Create a new DP table dp_curr.
For each pair (prev2, prev1) representing the last two elements:
For each candidate next_val in [0, m-1]:
Ensure next_val != prev1.
Ensure (prev2, prev1, next_val) does not form a strictly increasing or strictly decreasing sequence.
If valid, increment dp_curr[prev1][next_val] by dp_prev[prev2][prev1].
Replace dp_prev with dp_curr for the next iteration.
Sum all counts in dp_prev to get the total number of valid ZigZag arrays.
Return the result modulo 10^9 + 7.

Why it works: The DP invariant guarantees that dp_prev[a][b] always contains the number of valid arrays ending with (a, b) up to the current length. By only extending arrays with values that maintain the ZigZag property, we ensure that all arrays counted are valid and no valid array is missed.

Python Solution

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 10**9 + 7
        m = r - l + 1
        # Initialize DP for arrays of length 2
        dp_prev = [[0] * m for _ in range(m)]
        for a in range(m):
            for b in range(m):
                if a != b:
                    dp_prev[a][b] = 1

        for _ in range(3, n + 1):
            dp_curr = [[0] * m for _ in range(m)]
            for prev2 in range(m):
                for prev1 in range(m):
                    if dp_prev[prev2][prev1] == 0:
                        continue
                    for next_val in range(m):
                        if next_val == prev1:
                            continue
                        if (prev2 < prev1 < next_val) or (prev2 > prev1 > next_val):
                            continue
                        dp_curr[prev1][next_val] = (dp_curr[prev1][next_val] + dp_prev[prev2][prev1]) % MOD
            dp_prev = dp_curr

        return sum(sum(row) for row in dp_prev) % MOD

Explanation: We initialize the DP for arrays of length 2 because the ZigZag property only starts mattering with three elements. The nested loops check all possible extensions and skip invalid sequences. The modulo is applied in each update to prevent overflow.

Go Solution

func zigZagArrays(n int, l int, r int) int {
    const MOD = 1_000_000_007
    m := r - l + 1

    dpPrev := make([][]int, m)
    for i := 0; i < m; i++ {
        dpPrev[i] = make([]int, m)
        for j := 0; j < m; j++ {
            if i != j {
                dpPrev[i][j] = 1
            }
        }
    }

    for step := 3; step <= n; step++ {
        dpCurr := make([][]int, m)
        for i := 0; i < m; i++ {
            dpCurr[i] = make([]int, m)
        }
        for prev2 := 0; prev2 < m; prev2++ {
            for prev1 := 0; prev1 < m; prev1++ {
                if dpPrev[prev2][prev1] == 0 {
                    continue
                }
                for nextVal := 0; nextVal < m; nextVal++ {
                    if nextVal == prev1 {
                        continue
                    }
                    if (prev2 < prev1 && prev1 < nextVal) || (prev2 > prev1 && prev1 > nextVal) {
                        continue
                    }
                    dpCurr[prev1][nextVal] = (dpCurr[prev1][nextVal] + dpPrev[prev2][prev1]) % MOD
                }
            }
        }
        dpPrev = dpCurr
    }

    result := 0
    for i := 0; i < m; i++ {
        for j := 0; j < m; j++ {
            result = (result + dpPrev[i][j]) % MOD
        }
    }
    return result
}

Go-specific notes: Go requires explicit slice initialization. The modulo is applied similarly. Integer overflow is not an issue with int for these constraints but modulo ensures correctness.

Worked Examples

Example 1: n = 3, l = 4, r = 5

m = 2 → possible values [0,1] mapping [4,5].

Initialize dp_prev for length 2: dp_prev[0][1] = 1, dp_prev[1][0] = 1.
Extend to length 3: valid next_val only allows sequences [0,1,0] and [1,0,1].
Sum dp_prev → 2.

Example 2: n = 3, l = 1, r = 3

m = 3 → values [0,1,2] mapping [1,2,3].

Initialize dp_prev for length 2 → all pairs except identical values.
Extend to length 3 →