3700. Number of ZigZag Arrays II

  • Dynamic Programming
  • Matrix Exponentiation
  • Combinatorics
TIME
O(m^3 log n) where m = r - l + 1
SPACE
O(m^2)
problem on leetcode ↗source on github ↗

Intuition

This is the same counting problem as ZigZag I, but n can be up to 10^9, so the O(n * m) per-length DP is too slow. The DP transition is linear in the state, so we can advance many lengths at once with matrix exponentiation. Here m = r - l + 1 <= 75 is small, which makes an m x m matrix power cheap.

Approach

As in part I, define up[v] = number of zigzag sequences ending at value v whose last step went up. Using the mirror symmetry down[v] = up[m-1-v], the entire state reduces to the single vector up, advanced by one linear map per length:

new_up[v] = sum over w >= m - v of up[w]

This is multiplication by a fixed m x m matrix M with M[v][w] = 1 iff w >= m - v.

  1. Build M.
  2. Compute M^(n-1) by binary exponentiation (modular m x m matrix multiply).
  3. The initial vector is all ones (up at length 1), so up at length n is M^(n-1) applied to ones, i.e. each up[v] is a row sum of the power matrix. Their total is the sum of all entries of M^(n-1).
  4. By symmetry the grand total is 2 * (sum of all entries), taken modulo 10^9 + 7.

Complexity

  • Time: O(m^3 * log n), log n matrix multiplications of size m
  • Space: O(m^2), the matrices

Edge Cases

  • m = 2 -> answer 2 for any n (only the two alternating arrays)
  • Very large n (up to 10^9) -> handled by log n exponentiation steps
  • Modulo applied throughout to avoid overflow (use long accumulation in Java)
  • n - 1 exponent: length-1 base vector is the all-ones vector

Code

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        """
        3700. Number of ZigZag Arrays II
        Time: O(m^3 log n) where m = r - l + 1
        Space: O(m^2)
        """
        MOD = 10**9 + 7
        m = r - l + 1

        # Transition matrix: new_up[v] = sum_{w >= m - v} up[w].
        M = [[1 if w >= m - v else 0 for w in range(m)] for v in range(m)]

        def mul(A, B):
            B_cols = list(zip(*B))
            return [
                [sum(a * b for a, b in zip(row, col)) % MOD for col in B_cols]
                for row in A
            ]

        # Binary exponentiation of M to the (n - 1) power.
        result = [[int(i == j) for j in range(m)] for i in range(m)]
        power = n - 1
        base = M
        while power:
            if power & 1:
                result = mul(result, base)
            base = mul(base, base)
            power >>= 1

        # up at length n = result @ ones; total over v = sum of all entries.
        total_up = sum(sum(row) % MOD for row in result) % MOD
        return (2 * total_up) % MOD