LeetCode #3700 — HARD

Number of ZigZag Arrays II

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode
The Problem

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 109 + 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 <= 109
  • 1 <= l < r <= 75​​​​​​​
Patterns Used
📊Dynamic Programming→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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 109 + 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).

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Math · Dynamic Programming

Example 1

3
4
5

Example 2

3
1
3
Step 02

Core Insight

What unlocks the optimal approach

  • Use matrix exponentiation
  • Encode states in a vector of length <code>2*m</code> where <code>m = r - l + 1</code>: first <code>m</code> entries = "next compare = down" for values, next <code>m</code> = "next compare = up".
  • Build a transition matrix <code>T</code> (size <code>2*m × 2*m</code>): from an <code>up,x</code> state go to <code>down,y</code> for every <code>y > x</code>, and from <code>down,x</code> go to <code>up,y</code> for every <code>y < x</code>.
  • Use fast matrix exponentiation to compute <code>T^(n-1)</code>, apply it to the initial vector (ones in the block for starting <code>up</code> and separately for starting <code>down</code>), sum final entries, and add both results (for <code>n=1</code> return <code>m</code>).
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Largest constraint values
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3700: Number of ZigZag Arrays II
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3700: Number of ZigZag Arrays II
// package main
// 
// import (
// 	"fmt"
// 	"slices"
// )
// 
// // https://space.bilibili.com/206214
// type matrix [][]int
// 
// func newMatrix(n, m int) matrix {
// 	a := make(matrix, n)
// 	for i := range a {
// 		a[i] = make([]int, m)
// 	}
// 	return a
// }
// 
// // 返回 a*b
// func (a matrix) mul(b matrix) matrix {
// 	c := newMatrix(len(a), len(b[0]))
// 	for i, row := range a {
// 		for k, x := range row {
// 			if x == 0 {
// 				continue
// 			}
// 			for j, y := range b[k] {
// 				c[i][j] = (c[i][j] + x*y) % mod
// 			}
// 		}
// 	}
// 	return c
// }
// 
// // 返回 a^n * f1
// func (a matrix) powMul(n int, f1 matrix) matrix {
// 	res := f1
// 	for ; n > 0; n /= 2 {
// 		if n%2 > 0 {
// 			res = a.mul(res)
// 		}
// 		a = a.mul(a)
// 	}
// 	return res
// }
// 
// func zigZagArrays1(n, l, r int) (ans int) {
// 	k := r - l + 1
// 	m := newMatrix(k, k)
// 	for i := range k {
// 		for j := range k - 1 - i {
// 			m[i][j] = 1
// 		}
// 	}
// 
// 	f1 := newMatrix(k, 1)
// 	for i := range f1 {
// 		f1[i][0] = 1
// 	}
// 
// 	fn := m.powMul(n-1, f1)
// 	for _, row := range fn {
// 		ans += row[0]
// 	}
// 	return ans * 2 % mod
// }
// 
// //
// 
// const mod = 1_000_000_007
// 
// func pow(x, n int) int {
// 	res := 1
// 	for ; n > 0; n /= 2 {
// 		if n%2 > 0 {
// 			res = res * x % mod
// 		}
// 		x = x * x % mod
// 	}
// 	return res
// }
// 
// // 给定数列的前 m 项 a，返回符合 a 的最短常系数齐次线性递推式的系数 coef（模 mod 意义下）
// // 设 coef 长为 k，当 n >= k 时，有递推式 f(n) = coef[0] * f(n-1) + coef[1] * f(n-2) + ... + coef[k-1] * f(n-k)  （注意 coef 的顺序）
// // 初始值 f(n) = a[n]  (0 <= n < k)
// // 时间复杂度 O(m^2)，其中 m 是 a 的长度
// func berlekampMassey(a []int) (coef []int) {
// 	var preC []int
// 	preI, preD := -1, 0
// 
// 	for i, v := range a {
// 		// d = a[i] - 递推式算出来的值
// 		d := v
// 		for j, c := range coef {
// 			d = (d - c*a[i-1-j]) % mod
// 		}
// 		if d == 0 { // 递推式正确
// 			continue
// 		}
// 
// 		// 首次算错，初始化 coef 为 i+1 个 0
// 		if preI < 0 {
// 			coef = make([]int, i+1)
// 			preI, preD = i, d
// 			continue
// 		}
// 
// 		bias := i - preI
// 		oldLen := len(coef)
// 		newLen := bias + len(preC)
// 		var tmp []int
// 		if newLen > oldLen { // 递推式变长了
// 			tmp = slices.Clone(coef)
// 			coef = slices.Grow(coef, newLen-oldLen)[:newLen] // coef.resize(newLen)
// 		}
// 
// 		// 历史错误为 preD = a[preI] - sum_j preC[j]*a[preI-1-j]
// 		// 现在 a[i] = sum_j coef[j]*a[i-1-j] + d
// 		// 联立得 a[i] = sum_j coef[j]*a[i-1-j] + d/preD * (a[preI] - sum_j preC[j]*a[preI-1-j])
// 		// 其中 a[preI] 的系数 d/preD 位于当前（i）的 bias-1 = i-preI-1 处
// 		delta := d * pow(preD, mod-2) % mod // pow(preD, mod-2) 为 preD 的逆元
// 		coef[bias-1] = (coef[bias-1] + delta) % mod
// 		for j, c := range preC {
// 			coef[bias+j] = (coef[bias+j] - delta*c) % mod
// 		}
// 
// 		if newLen > oldLen {
// 			preC = tmp
// 			preI, preD = i, d
// 		}
// 	}
// 
// 	// 计算完后，可能 coef 的末尾有 0，这些 0 不能去掉
// 	// 比如数列 (1,2,4,2,4,2,4,...) 的系数为 [0,1,0]，表示 f(n) = 0*f(n-1) + 1*f(n-2) + 0*f(n-3) = f(n-2)   (n >= 3)
// 	// 如果把末尾的 0 去掉，变成 [0,1]，就表示 f(n) = 0*f(n-1) + f(n-2) = f(n-2)   (n >= 2)
// 	// 看上去一样，但按照这个式子算出来的数列是错误的 (1,2,1,2,1,2,...)
// 
// 	// 手动找规律用
// 	for i, c := range coef {
// 		if c < -mod/2 {
// 			c += mod
// 		} else if c > mod/2 {
// 			c -= mod
// 		}
// 		coef[i] = c
// 	}
// 
// 	return
// }
// 
// // 给定常系数齐次线性递推式 f(n) = coef[k-1] * f(n-1) + coef[k-2] * f(n-2) + ... + coef[0] * f(n-k)
// // 以及初始值 f(i) = a[i] (0 <= i < k)
// // 返回 f(n) % mod，其中参数 n 从 0 开始
// // 注意 coef 的顺序
// // 时间复杂度 O(k^2 log n)，其中 k 是 coef 的长度
// func kitamasa(coef, a []int, n int) (ans int) {
// 	defer func() { ans = (ans + mod) % mod }() // 保证结果非负
// 	if n < len(a) {
// 		return a[n] % mod
// 	}
// 
// 	k := len(coef)
// 	// 特判 k = 0, 1 的情况
// 	if k == 0 {
// 		return 0
// 	}
// 	if k == 1 {
// 		return a[0] * pow(coef[0], n) % mod
// 	}
// 
// 	// 已知 f(n) 的各项系数为 a，f(m) 的各项系数为 b
// 	// 计算并返回 f(n+m) 的各项系数 c
// 	compose := func(a, b []int) []int {
// 		c := make([]int, k)
// 		for _, v := range a {
// 			for j, w := range b {
// 				c[j] = (c[j] + v*w) % mod
// 			}
// 			// 原地计算下一组系数，比如已知 f(4) 的各项系数，现在要计算 f(5) 的各项系数
// 			// 倒序遍历，避免提前覆盖旧值
// 			bk1 := b[k-1]
// 			for i := k - 1; i > 0; i-- {
// 				b[i] = (b[i-1] + bk1*coef[i]) % mod
// 			}
// 			b[0] = bk1 * coef[0] % mod
// 		}
// 		return c
// 	}
// 
// 	// 计算 resC，以表出 f(n) = resC[k-1] * a[k-1] + resC[k-2] * a[k-2] + ... + resC[0] * a[0]
// 	resC := make([]int, k)
// 	resC[0] = 1
// 	c := make([]int, k)
// 	c[1] = 1
// 	for ; n > 0; n /= 2 {
// 		if n%2 > 0 {
// 			resC = compose(c, resC)
// 		}
// 		// 由于会修改 compose 的第二个参数，这里把 c 复制一份再传入
// 		c = compose(c, slices.Clone(c))
// 	}
// 
// 	for i, c := range resC {
// 		ans = (ans + c*a[i]) % mod
// 	}
// 
// 	return
// }
// 
// // 见上一题 3699. 锯齿形数组的总数 I
// func zigZagArraysInit(l, r int) []int {
// 	k := r - l + 1
// 	f := make([]int, k)
// 	for i := range f {
// 		f[i] = 1
// 	}
// 
// 	a := make([]int, k*2)
// 	for i := range a {
// 		pre := 0
// 		s := 0
// 		for j, v := range f {
// 			f[j] = pre % mod
// 			pre += v
// 			s += f[j]
// 		}
// 		a[i] = s * 2 % mod
// 		slices.Reverse(f)
// 	}
// 	return a
// }
// 
// func zigZagArrays(n, l, r int) int {
// 	a := zigZagArraysInit(l, r)
// 	coef := berlekampMassey(a)
// 	fmt.Println(len(coef))
// 	//fmt.Println(a, coef)
// 	//fmt.Println(coef)
// 	slices.Reverse(coef) // 注意 kitamasa 入参的顺序
// 	return kitamasa(coef, a, n-2)
// }
// 
// func main() {
// 	for r := 1; r <= 15; r++ {
// 		zigZagArrays(1e9, 0, r)
// 	}
// }
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(n × m)
Space
O(n × m)

Approach Breakdown

RECURSIVE
O(2ⁿ) time
O(n) space

Pure recursion explores every possible choice at each step. With two choices per state (take or skip), the decision tree has 2ⁿ leaves. The recursion stack uses O(n) space. Many subproblems are recomputed exponentially many times.

DYNAMIC PROGRAMMING
O(n × m) time
O(n × m) space

Each cell in the DP table is computed exactly once from previously solved subproblems. The table dimensions determine both time and space. Look for the state variables — each unique combination of state values is one cell. Often a rolling array can reduce space by one dimension.

Shortcut: Count your DP state dimensions → that’s your time. Can you drop one? That’s your space optimization.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

State misses one required dimension

Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.

Usually fails on: Correctness breaks on cases that differ only in hidden state.

Fix: Define state so each unique subproblem maps to one DP cell.

Related Problems
#62Unique Pathsmedium→#70Climbing Stairseasy→#96Unique Binary Search Treesmedium→#233Number of Digit Onehard→#241Different Ways to Add Parenthesesmedium→