3699. Number of ZigZag Arrays I

Problem Statement

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^9 + 7$.

A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if it exists).

A sequence is said to be strictly decreasing if each element is strictly smaller than its previous one (if it exists).

Solution

The problem asks for the number of ZigZag arrays of length n with elements in the range [l, r]. The constraints are $3 \le n \le 2000$ and $1 \le l < r \le 2000$.

First, we can simplify the problem by normalizing the range. The absolute values of l and r don’t matter, only the size of the range. We can map the range [l, r] to [1, r - l + 1]. Let m = r - l + 1.

This problem can be solved using dynamic programming. We need to build the array element by element, keeping track of the necessary information to satisfy the ZigZag conditions. The state of our DP should encode the current position we are filling, the value of the last element, and the direction of the last change (i.e., whether the previous element was smaller or larger).

Let dp[i][j][k] be the number of valid ZigZag arrays of length i where the i-th element is j, and k indicates the relationship between the last two elements:

• k = 0: The sequence is “pointing up” at the end, meaning A[i-1] < A[i]. The next element A[i+1] must be smaller than A[i].
• k = 1: The sequence is “pointing down” at the end, meaning A[i-1] > A[i]. The next element A[i+1] must be greater than A[i].

Base Case: For an array of length 2, A[1], A[2]:

• dp[2][j][0] (for A[1] < A[2]=j): A[1] can be any value from 1 to j-1. So there are j-1 possibilities.
• dp[2][j][1] (for A[1] > A[2]=j): A[1] can be any value from j+1 to m. So there are m-j possibilities.

Transitions: For i > 2:

• To compute dp[i][j][0] (ending with ... < j), the previous state must have been dp[i-1][p][1] where p > j. This ensures the ZigZag pattern (... > p < j is not allowed). So, we need A[i-2] > A[i-1] and A[i-1] < A[i]. The previous state must have been pointing down. $dp[i][j][0] = \sum_{p=j+1}^{m} dp[i-1][p][1]$
• To compute dp[i][j][1] (ending with ... > j), the previous state must have been dp[i-1][p][0] where p < j. This ensures the ZigZag pattern (... < p > j is not allowed). So, we need A[i-2] < A[i-1] and A[i-1] > A[i]. The previous state must have been pointing up. $dp[i][j][1] = \sum_{p=1}^{j-1} dp[i-1][p][0]$

The summations can be optimized using prefix sums (or in this case, suffix sums for the first transition). For a fixed i, as we calculate dp[i][j][k] for j from 1 to m, we can maintain the running sum of the required dp[i-1] values.

Optimization: We can observe that dp[i] only depends on dp[i-1]. This means we can optimize the space complexity from $O(n \cdot m)$ to $O(m)$ by using only two arrays to store the DP states for the current and previous lengths. The provided code uses a 3D array, but the logic can be implemented with space optimization.

The final answer is the sum of all dp[n][j][k] for all valid j and k.

static const auto fast_io = []() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    return 0;
}();
#define N 2005
class Solution {
public:
    int mod = 1e9 + 7;
    int dp[N][N][2];
    int zigZagArrays(int n, int l, int r) {
        r -= l;
        r++;
        l = 1;
        int ans = 0;
        // 0 next need incresing, 1 next need to descring
        for (int i = 1; i < r + 1; i++) {
            dp[2][i][0] = r - i;
            dp[2][i][1] = i - 1;
        }
        for (int i = 3; i <= n; i++) {
            int tmp1 = 0;
            for (int j = 1; j < r + 1; j++) {
                dp[i][j][1] = tmp1;
                tmp1 += dp[i - 1][j][0];
                dp[i][j][1] %= mod;
                tmp1 %= mod;
            }
            tmp1 = 0;
            for (int j = r; j >= 1; j--) {
                dp[i][j][0] = tmp1;
                tmp1 += dp[i - 1][j][1];
                dp[i][j][0] %= mod;
                tmp1 %= mod;
            }
        }

        // sum of dp[n][all j][all k]
        for (int i = 1; i < r + 1; i++) {
            ans += dp[n][i][0];
            ans %= mod;
            ans += dp[n][i][1];
            ans %= mod;
        }
        return ans;
    }
};

Time and Space Complexity

• Time Complexity: $O(n \cdot (r-l))$. We iterate n times, and for each i, we iterate through all m = r-l+1 possible values.
• Space Complexity: $O(n \cdot (r-l))$ for the DP table. This can be optimized to $O(r-l)$ since dp[i] only depends on dp[i-1].