LeetCode Entry

3699. Number of ZigZag Arrays I

23.06.2026 hard 2026 kotlin rust

Ways to make l..r zigzag sequence

3699. Number of ZigZag Arrays I hard substack youtube

https://dmitrysamoylenko.com/leetcode/

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1399

Problem TLDR

Ways to make l..r zigzag sequence

Intuition

Didn’t solve.

    // 15 minute: TLE, O(n^3), hint: prefix sums?
    // f(i, p, 1) = f(i+1, l, 2) + f(i+1, l+1, 2) + ... f(i+1, p-1, 2)

    // f(i, p, 2) = f(i+1, p+1, 1) + f(i+1, p+2, 1)+...+f(i+1,r,1)

    // f(i+1, l, 2) = f(i+2, l+1, 1) + f(i+2, l+2, 1) + ... f(i+2, p-1, 1)

    // f(i+1, p+1, 1) = f(i+2, l, 2) + f(i+2, l+1, 2)+...+f(i+2,p,2)
    // 28 minute: give up
    //
    // f(i,p,1) = sum{k=l..p-1}(f(i+1,k,2))
    // f(i,p-1,1) = sum{k=l..p-2}(f(i+1,k,2))
    // f(i,p,1)-f(i,p-1,1)=f(i+1,p-1,2)
    // f(i,p,1)=f(i,p-1,1)+f(i+1,p-1,2)
    // f(i,p,2)=f(i,p+1,2)+f(i+1,p+1,1)

Top down O(n^2) can be derived (see above), but still gives TLE. Bottom up: 1) move range to 0..r-l 2) use symmetry *2 3) dp[v] is the number of arrays ending with value v 4) dp[v]=sum(dp[0..v]) odd and sum(dp[v..r-l]) even 5) the sum(dp[..]) is just a running sum variable

Approach

• not sure if I could solve this or similar next time, the jump to bottom up is not obvious

Complexity

• Time complexity: \(O(n^2)\)

• Space complexity: \(O(n)\)

Code

    fun zigZagArrays(n: Int, l: Int, r: Int): Int {
        val r = r-l; val M = 1000000007; val dp = IntArray(r+1){1}
        for (i in 1..<n) {
            var pre = 0
            for (v in if (i%2>0) 0..r else r downTo 0)
                { val pre2 = pre + dp[v]; dp[v] = pre; pre = pre2%M }
        }
        return dp.fold(0){r,t->(r+t)%M}*2%M
    }

    pub fn zig_zag_arrays(n: i32, l: i32, r: i32) -> i32 {
        let r = (r-l+1) as usize; let M = 1000000007; let mut dp = vec![1;r];
        for i in 1..n {
            let mut s = 0;
            if i & 1 > 0 { for v in 0..r { s=(s+replace(&mut dp[v],s))%M} }
            else { for v in (0..r).rev() { s=(s+replace(&mut dp[v],s))%M} }
        }
        (dp.iter().fold(0, |s, &t| (s+t)%M)*2%M) as _
    }