Skip to main content
Talentd

Number of ZigZag Arrays I - Solution & Explanation

HardDynamic ProgrammingPrefix Sum4 min readAsked at: Amazon, Microsoft, Meta +2
Practice this 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 <= 2000
  • 1 <= l < r <= 2000

Approach Overview

Problem 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.

Solution

Code

C

C

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Dynamic ProgrammingO(n * m^2)O(n * m)Good for understanding the DP transition and zigzag constraint when value range is small
DP with Prefix Sum OptimizationO(n * m)O(n * m)Preferred solution for large constraints where scanning all previous values is too slow

Video Solution

Number of ZigZag Arrays I | Brute Force | Better | Optimal | Leetcode 3699 | codestorywithMIK ā€¢ codestorywithMIK ā€¢ 11,434 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Number of ZigZag Arrays I easy or hard?
Number of ZigZag Arrays I is classified as Hard because the naive DP approach is not sufficient for large inputs. Recognizing that prefix sums can optimize the DP transitions is the key insight that reduces the complexity and makes the problem feasible.
Number of ZigZag Arrays I Python/Java solution
Implement a DP table where dp[i][v] represents the number of ways to end position i with value v. Maintain prefix sums for each row so transitions for smaller or larger values can be computed in O(1). The same logic translates directly across Python, Java, C++, and Go.
How to solve Number of ZigZag Arrays I in O(n)?
Pure O(n) time is not typical because the algorithm must consider all possible values for each position. The practical optimal solution is O(n * m) using dynamic programming and prefix sums, where prefix sums eliminate the inner loop used in the brute force transition.
What is the best approach for Number of ZigZag Arrays I?
The most efficient approach uses dynamic programming with prefix sums. Define dp[i][v] as the number of zigzag arrays of length i ending with value v. Prefix sums allow constant-time range queries for transitions that require smaller or larger previous values, reducing the complexity to O(n * m).
Is Number of ZigZag Arrays I asked at Google/Amazon/Meta?
Zigzag counting problems frequently appear in interviews at large tech companies such as Google, Amazon, and Meta because they combine dynamic programming with range-sum optimization. Variants often test whether candidates can optimize DP transitions using prefix sums.
What data structure is used in Number of ZigZag Arrays I?
The solution primarily uses a dynamic programming table along with prefix sum arrays. The prefix sums allow fast range queries over previous DP states, which avoids scanning all values during each transition.
What is the time complexity of Number of ZigZag Arrays I?
The optimized solution runs in O(n * m) time using dynamic programming with prefix sums, where n is the array length and m is the value range. A naive dynamic programming approach without prefix sums takes O(n * m^2) time because it checks all previous values for every state.

Ready to solve this problem?

Practice Number of ZigZag Arrays I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching