Abhinav Faujdar

Given an array, find the no. of zig-zag sub-sequences in it. A Zig-zag sequence has to be of odd length and if it starts with x, every odd positioned element needs to be x. Even positioned elements can be either x+1 or x-1.

Level: Easy

Explanation: We can use hashmap. We can store a pair of <value,state> in hashmap as key corresponding to last element of the sequence (and the count of all such sequences as the value for that key). State can be 0,-1 or 1. 0→ odd element , 1→ even element (x+1) , -1 → even element(x-1). Update hashmap while traversing array.

Complexity: O(NlogN)