Watch 4 video solutions for Number of ZigZag Arrays I, a hard level problem involving Dynamic Programming, Prefix Sum. This walkthrough by Sanyam IIT Guwahati has 2,040 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given three integers n, l, and r.
A ZigZag array of length n is defined as follows:
[l, r].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 <= 20001 <= l < r <= 2000Problem Overview: Count how many arrays of length n form a valid zigzag pattern where adjacent comparisons alternate (a1 < a2 > a3 < a4 ... or the reverse). The challenge is counting all valid combinations while respecting value limits without enumerating every possible array.
Approach 1: Brute Force Dynamic Programming (O(n * m^2) time, O(n * m) space)
Define dp[i][v] as the number of ways to build a zigzag array of length i ending with value v. The direction of the inequality depends on the index parity: at one step you require smaller values, at the next step larger values. For each state, iterate over all possible previous values that satisfy the inequality condition. This results in a nested transition where every value checks up to m candidates, leading to O(n * m^2) time. The approach is straightforward and useful for understanding the zigzag constraint but becomes too slow when m is large.
Approach 2: Dynamic Programming with Prefix Sums (O(n * m) time, O(n * m) space)
The optimization removes the inner loop using prefix sums. Instead of scanning all previous values, maintain cumulative sums so you can instantly compute the number of valid smaller or larger values. For example, when the next step requires a value greater than the previous one, you query the prefix sum of all smaller values; when it requires a smaller value, you query the suffix range. Each transition becomes O(1), reducing the overall complexity to O(n * m). This technique is a classic combination of dynamic programming and prefix sum range queries.
The DP table is filled level by level for array positions. After computing each row, rebuild prefix sums so the next transition can access cumulative counts quickly. Modulo arithmetic is typically used to prevent overflow since the number of arrays grows rapidly.
Recommended for interviews: The prefix-sum optimized DP is what interviewers expect. Starting with the O(n * m^2) formulation shows you understand the state transition. Converting it to O(n * m) using prefix sums demonstrates optimization skills and strong familiarity with dynamic programming patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Dynamic Programming | O(n * m^2) | O(n * m) | Good for understanding the DP transition and zigzag constraint when value range is small |
| DP with Prefix Sum Optimization | O(n * m) | O(n * m) | Preferred solution for large constraints where scanning all previous values is too slow |