3699. Number of ZigZag Arrays I

Description

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 <= 2000
1 <= l < r <= 2000

Solutions

Solution 1: Dynamic Programming

Thinking

A zigzag array alternates the sign of consecutive differences. Values lie in \([l,r]\) and \(n\le 2000\), so we shift the range to \([0,m-1]\) and DP.

\(\textit{up}[i]\) and \(\textit{down}[i]\) count arrays ending at \(i\) whose last step rises or falls. A descent sums all larger \(\textit{up}\); an ascent sums all smaller \(\textit{down}\).

Prefix and suffix sums make each of the \(n-1\) rounds \(O(m)\). Length \(1\) seeds both directions with \(1\). Reduce the total modulo \(10^9+7\).

Let \(m = r - l + 1\) and map the range \([l, r]\) to \([0, m - 1]\).

Let \(up[i]\) be the number of arrays of the current length that end with \(i\) whose last step is an increase, and \(down[i]\) the number whose last step is a decrease. For length \(1\) there is no direction, so initialize \(up[i] = down[i] = 1\).

Transitions:

If the array ends at \(i\) with a decrease, the previous value must be greater than \(i\) and the previous step must be an increase: \(down'[i] = \sum_{j > i} up[j]\);
If the last step is an increase: \(up'[i] = \sum_{j < i} down[j]\).

Prefix and suffix sums make each transition \(O(m)\). Repeat \(n - 1\) times. The answer is the sum of all \(up[i] + down[i]\).

The time complexity is \(O(n \times m)\), and the space complexity is \(O(m)\), where \(n\) is the array length and \(m\) is the size of the value range.

Python3JavaC++GoC

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        mod = 10**9 + 7
        m = r - l + 1
        up = [1] * m
        down = [1] * m
        for _ in range(n - 1):
            pre = [0] * (m + 1)
            suf = [0] * (m + 1)
            for i in range(m):
                pre[i + 1] = (pre[i] + down[i]) % mod
            for i in range(m - 1, -1, -1):
                suf[i] = (suf[i + 1] + up[i]) % mod
            up = pre[:m]
            down = suf[1:]
        return sum(up + down) % mod

class Solution {
    public int zigZagArrays(int n, int l, int r) {
        final int mod = (int) 1e9 + 7;
        int m = r - l + 1;
        long[] up = new long[m];
        long[] down = new long[m];
        Arrays.fill(up, 1);
        Arrays.fill(down, 1);
        for (int k = 1; k < n; ++k) {
            long[] pre = new long[m + 1];
            long[] suf = new long[m + 1];
            for (int i = 0; i < m; ++i) {
                pre[i + 1] = (pre[i] + down[i]) % mod;
            }
            for (int i = m - 1; i >= 0; --i) {
                suf[i] = (suf[i + 1] + up[i]) % mod;
            }
            for (int i = 0; i < m; ++i) {
                up[i] = pre[i];
                down[i] = suf[i + 1];
            }
        }
        long ans = 0;
        for (int i = 0; i < m; ++i) {
            ans = (ans + up[i] + down[i]) % mod;
        }
        return (int) ans;
    }
}

class Solution {
public:
    int zigZagArrays(int n, int l, int r) {
        const int mod = 1e9 + 7;
        int m = r - l + 1;
        vector<long long> up(m, 1), down(m, 1);
        for (int k = 1; k < n; ++k) {
            vector<long long> pre(m + 1), suf(m + 1);
            for (int i = 0; i < m; ++i) {
                pre[i + 1] = (pre[i] + down[i]) % mod;
            }
            for (int i = m - 1; i >= 0; --i) {
                suf[i] = (suf[i + 1] + up[i]) % mod;
            }
            for (int i = 0; i < m; ++i) {
                up[i] = pre[i];
                down[i] = suf[i + 1];
            }
        }
        long long ans = 0;
        for (int i = 0; i < m; ++i) {
            ans = (ans + up[i] + down[i]) % mod;
        }
        return ans;
    }
};

func zigZagArrays(n int, l int, r int) int {
    const mod = int64(1e9 + 7)
    m := r - l + 1
    up := make([]int64, m)
    down := make([]int64, m)
    for i := range up {
        up[i], down[i] = 1, 1
    }
    for k := 1; k < n; k++ {
        pre := make([]int64, m+1)
        suf := make([]int64, m+1)
        for i := 0; i < m; i++ {
            pre[i+1] = (pre[i] + down[i]) % mod
        }
        for i := m - 1; i >= 0; i-- {
            suf[i] = (suf[i+1] + up[i]) % mod
        }
        for i := 0; i < m; i++ {
            up[i] = pre[i]
            down[i] = suf[i+1]
        }
    }
    var ans int64
    for i := 0; i < m; i++ {
        ans = (ans + up[i] + down[i]) % mod
    }
    return int(ans)
}

int zigZagArrays(int n, int l, int r) {
    int mod = 1e9 + 7;
    int m = r - l + 1;
    long long up[m], down[m];
    for (int i = 0; i < m; ++i) {
        up[i] = down[i] = 1;
    }
    for (int k = 1; k < n; ++k) {
        long long pre[m + 1], suf[m + 1];
        memset(pre, 0, sizeof(pre));
        memset(suf, 0, sizeof(suf));
        for (int i = 0; i < m; ++i) {
            pre[i + 1] = (pre[i] + down[i]) % mod;
        }
        for (int i = m - 1; i >= 0; --i) {
            suf[i] = (suf[i + 1] + up[i]) % mod;
        }
        for (int i = 0; i < m; ++i) {
            up[i] = pre[i];
            down[i] = suf[i + 1];
        }
    }
    long long ans = 0;
    for (int i = 0; i < m; ++i) {
        ans = (ans + up[i] + down[i]) % mod;
    }
    return ans;
}

3699. Number of ZigZag Arrays I

Description

Solutions

Solution 1: Dynamic Programming

Comments