LeetCode 3700 - Number of ZigZag Arrays II

LeetCode Problem 3700

Difficulty: 🔴 Hard
Topics: Math, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count the number of arrays of length n where each element is in the range [l, r], no two consecutive elements are equal, and no three consecutive elements are strictly increasing or strictly decreasing. These arrays are termed ZigZag arrays.

In other words, for an array A of length n:

1. For all i, l <= A[i] <= r.
2. For all i in [0, n-2], A[i] != A[i+1].
3. For all i in [0, n-3], the triplet (A[i], A[i+1], A[i+2]) is not strictly increasing nor strictly decreasing.

The input n can be very large, up to 10^9, which rules out brute-force enumeration of all possible arrays. The range [l, r] is small (<=75), which suggests a dynamic programming approach over the values rather than the positions is feasible. The answer must be returned modulo 10^9 + 7.

Edge cases to consider include l and r being consecutive (e.g., r-l=1), where choices are severely limited, and small n values where patterns might not even reach three elements.

Approaches

The brute-force approach would generate all possible sequences of length n in the range [l, r] and filter them according to the ZigZag rules. This would involve O((r-l+1)^n) sequences, which is completely infeasible for large n. Even recursive backtracking with memoization is impractical due to n up to 10^9.

The optimal approach leverages the observation that the problem has recurrence and symmetry properties. Specifically, the constraints only depend on the last two elements of the array. Therefore, we can model the problem as a matrix exponentiation problem. Let dp[a][b] represent the number of valid sequences ending with the last two elements being (a, b). Then, to compute the next element c, we only need to check c != b and that (a, b, c) does not form a strictly increasing or decreasing sequence. This forms a transition matrix, which can be exponentiated efficiently to compute sequences of length n.

Algorithm Walkthrough

1. Define m = r - l + 1 as the number of possible values in the array. Each value can be mapped to 0..m-1 for simplicity.
2. Construct all valid transitions between pairs (a, b) and the next value c. A transition is valid if c != b and (a, b, c) is not strictly increasing nor decreasing.
3. Encode all pairs (a, b) as indices from 0 to m^2-1. Construct a transition matrix T of size m^2 x m^2 where T[i][j] = 1 if pair j can follow pair i.
4. The initial vector v represents all valid sequences of length 2. Since any two distinct numbers (a, b) are allowed, set v[i] = 1 if a != b.
5. Compute T^(n-2) using fast matrix exponentiation. Multiply it by v to get the number of sequences of length n.
6. Sum all entries in the resulting vector modulo 10^9 + 7 to get the total number of ZigZag arrays.

Why it works: The key invariant is that the constraints only depend on the last two elements. By encoding all possible pairs and transitions, we guarantee that all sequences counted satisfy the ZigZag conditions. Matrix exponentiation allows efficient computation for large n.

Python Solution

class Solution:
    MOD = 10**9 + 7

    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        m = r - l + 1
        size = m * m

        def index(a, b):
            return a * m + b

        # Build transition matrix
        T = [[0] * size for _ in range(size)]
        for a in range(m):
            for b in range(m):
                if a == b:
                    continue
                for c in range(m):
                    if c == b:
                        continue
                    if (a < b < c) or (a > b > c):
                        continue
                    T[index(a, b)][index(b, c)] = 1

        # Initial vector for sequences of length 2
        vec = [0] * size
        for a in range(m):
            for b in range(m):
                if a != b:
                    vec[index(a, b)] = 1

        def mat_mult(A, B):
            n = len(A)
            m = len(B[0])
            p = len(B)
            C = [[0]*m for _ in range(n)]
            for i in range(n):
                for k in range(p):
                    if A[i][k] == 0:
                        continue
                    for j in range(m):
                        C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % self.MOD
            return C

        def mat_pow(mat, power):
            n = len(mat)
            res = [[1 if i==j else 0 for j in range(n)] for i in range(n)]
            while power:
                if power % 2:
                    res = mat_mult(res, mat)
                mat = mat_mult(mat, mat)
                power //= 2
            return res

        # Exponentiate matrix to length n-2
        if n == 2:
            return sum(vec) % self.MOD
        Tn = mat_pow(T, n-2)
        # Multiply Tn with initial vector
        res = 0
        for i in range(size):
            for j in range(size):
                res = (res + Tn[i][j] * vec[j]) % self.MOD
        return res

The Python code first encodes the transitions for all valid pairs. It uses matrix multiplication and exponentiation to scale for large n. The final multiplication with the initial vector counts all sequences of length n.

Go Solution

package main

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

    index := func(a, b int) int {
        return a*m + b
    }

    // Build transition matrix
    T := make([][]int, size)
    for i := range T {
        T[i] = make([]int, size)
    }
    for a := 0; a < m; a++ {
        for b := 0; b < m; b++ {
            if a == b {
                continue
            }
            for c := 0; c < m; c++ {
                if c == b {
                    continue
                }
                if (a < b && b < c) || (a > b && b > c) {
                    continue
                }
                T[index(a, b)][index(b, c)] = 1
            }
        }
    }

    // Initial vector
    vec := make([]int, size)
    for a := 0; a < m; a++ {
        for b := 0; b < m; b++ {
            if a != b {
                vec[index(a, b)] = 1
            }
        }
    }

    matMult := func(A, B [][]int) [][]int {
        n := len(A)
        m := len(B[0])
        p := len(B)
        C := make([][]int, n)
        for i := 0; i < n; i++ {
            C[i] = make([]int, m)
            for k := 0; k < p; k++ {
                if A[i][k] == 0 {
                    continue
                }
                for j := 0; j < m; j++ {
                    C[i][j] = (C[i][j] + A[i][k]*B[k][j]) % MOD
                }
            }
        }
        return C
    }

    matPow := func(mat [][]int, power int) [][]int {
        n := len(mat)
        res := make([][]int, n)
        for i := 0; i < n; i++ {
            res[i] = make([]int, n)
            res[i][i] = 1
        }
        for power > 0 {
            if power%2 == 1 {
                res = matMult(res, mat)
            }
            mat = matMult(mat, mat)
            power /= 2
        }
        return res
    }

    if n == 2 {
        sum :=