Problem Statement in English

You are given three integers n, l, and r. You need to find the number of zig-zag arrays of length n where each element is an integer between l and r (inclusive). A zig-zag array is defined as an array where the elements alternate between increasing and decreasing.

Return the number of such zig-zag arrays modulo $10^9 + 7$.

Approach

There’s 2 parts to this problem:

  1. Finding the overlapping subproblems and defining the state of the dynamic programming solution.
  2. Figuring out how to account for the zig-zag property in the dynamic programming solution.
  3. Ensuring that we use the results of the previous subproblem/iteration to compute the current subproblem/iteration.

Which pattern do we start from? Increasing or decreasing? It doesn’t matter – we pick an arbitrary pattern, because we can just multiply the final answer by 2 to account for both cases.

So! Let’s solve it piece by piece.

1. The Overlapping Subproblem

First off, we’re going to define our answer to an arbitrary pattern of length n as the number of different numbers that could come before the current number, such that we’re able to end that pattern with the current number.

So let’s say we have an array of length $3$. Our answer would be the solution to the subproblem of length $2$ added to the solution to the subproblem of length $1$, and then we would append the current number to the end of that pattern. So our answer to the nth subproblem is the sum of the answers to all preceeding n - 1 subproblems.

2. Accounting for the Zig-Zag Property

What do we have to do when the next element has to be greater than the current element?

Suppose after some iteration we have the following dp array:

dp[j] = number of arrays ending with value j
  • Now suppose the next comparison should be up.

To end at value j, the previous value must be smaller:

new_dp[j] = dp[0] + dp[1] + ... + dp[j-1]

This is a prefix sum.

  • Now suppose the next comparison should be down.

To end at value j, the previous value must be larger:

new_dp[j] = dp[j+1] + dp[j+2] + ... + dp[m-1]

This is a suffix sum.

So the two recurrences are:

UP   : prefix sums
DOWN : suffix sums
  • Let’s look at an example to see how this works.
dp = [2, 5, 3, 7]

Let’s label the values:

value A -> 2
value B -> 5
value C -> 3
value D -> 7

Suppose we want suffix sums.

For value A:

5 + 3 + 7 = 15

For value B:

3 + 7 = 10

For value C:

7

For value D:

0

Result:

[15,10,7,0]
  • Now reverse the array.
[7,3,5,2]

Now compute prefix sums.

index 0 -> 0

index 1 -> 7

index 2 -> 7+3 = 10

index 3 -> 7+3+5 = 15

Result:

[0,7,10,15]

Now look carefully.

Reverse that result.

[15,10,7,0]

That’s exactly the suffix sums we wanted!

So mathematically,

suffix sums
=
reverse
→ prefix sums
→ reverse back

The reverse converts “everything after me” into “everything before me.”

  • Then why doesn’t the code reverse back?

This is the cleverest part.

Notice the next iteration is going to reverse again anyway.

So instead of doing

reverse
prefix
reverse

every iteration,

the author leaves the array reversed.

On the next iteration, the very first line is

dp.reverse()

which restores the normal order.

The code is essentially “carrying” the reversal from one iteration to the next instead of undoing it immediately.

And we’re done!

Solution in Python


class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 1000000007
        m = r - l + 1
        dp = [1] * m

        for i in range(2, n + 1):
            dp.reverse()
            s = 0

            for j in range(m):
                old = dp[j]
                dp[j] = s
                s = s + old
        
        return ((sum(dp) % MOD) * 2) % MOD

Complexity

  • Time: $O(n \cdot m)$
    Since we have a nested loop where the outer loop runs n times and the inner loop runs m times, the overall time complexity is $O(n \cdot m)$, where n is the number of elements in the zig-zag array and m is the range of values from l to r.

  • Space: $O(m)$
    The space complexity is $O(m)$ because we are using a single list dp of size m to store the number of valid zig-zag arrays for each possible value in the range from l to r.

And we are done.