Number of ZigZag Arrays II - Solution & Explanation

Problem Overview: You need to count how many arrays satisfy a zigzag pattern, where adjacent elements strictly alternate between increasing and decreasing. The task is combinatorial in nature, and brute-force generation quickly becomes infeasible as the array length grows.

Approach 1: Brute Force Enumeration (Exponential Time, O(n) Space)

The most direct idea is to generate every possible array and check whether it satisfies the zigzag condition. During generation, compare each adjacent pair and ensure the relationship alternates between < and >. This approach uses recursion or backtracking and keeps track of the previous value and the expected direction. While simple to reason about, the search space grows exponentially with the array length, leading to O(m^n) time complexity and O(n) recursion stack space.

Approach 2: Dynamic Programming with Direction State (O(n * m^2) Time, O(n * m) Space)

A better approach models the problem using dynamic programming. Let dp[i][v][d] represent the number of valid zigzag arrays of length i that end with value v, where d indicates whether the previous step was increasing or decreasing. To transition, iterate through all valid previous values that satisfy the required relation (smaller values for an increasing step, larger values for a decreasing step). This captures the alternating constraint explicitly, but each transition may scan many candidate values, producing O(n * m^2) time.

Approach 3: DP with Prefix Sum Optimization (O(n * m) Time, O(n * m) Space)

The optimized solution removes the inner scan using prefix sums. Instead of iterating over all smaller or larger values, maintain cumulative counts so each transition becomes a constant-time lookup. For example, when computing increasing states, you sum all counts from values smaller than the current value using a prefix array. For decreasing states, use a suffix or reversed prefix sum. This transforms the DP transition into O(1), reducing the total complexity to O(n * m) time and O(n * m) space. The approach combines ideas from math counting techniques and efficient DP transitions.

Recommended for interviews: Start by explaining the brute-force generation to show you understand the zigzag constraint. Then transition to the DP formulation that tracks the last value and direction. Interviewers typically expect the prefix-sum optimized DP because it demonstrates strong command of dynamic programming state design and transition optimization.