Wave Generation

Problem Statement

Wave Generation Problem Description A sequence is called a wave when its values strictly zig-zag: every step goes the opposite way from the step before it. Using 1-based positions, an array a of length n is a wave if it follows one of these two patterns: Pattern A: a[1] > a[2] < a[3] > a[4] < ... (the first step goes down) Pattern B: a[1] < a[2] > a[3] < a[4] > ... (the first step goes up) Every comparison is strict, so two equal neighbours never form part of a wave. You are given an array arr of n integers. Each entry is either a fixed value between 1 and m , or -1 , which marks a blank. Every blank must be filled with an integer from 1 to m (blanks are filled independently, and the same value may be used many times). Fixed values stay as they are. Count the number of ways to fill all the blanks so that the finished array is a wave. Two ways are different when the finished arrays differ in at least one position. Because the count can be very large, return it mo