Zig Zag Subsequence

Hard
0/120
Average time to solve is 25m
7 upvotes
Asked in companies
OlaMorgan StanleyLTI - Larsen & Toubro Infotech

Problem statement

Ninja on his way to home found ‘N’ tokens on the ground arranged in a line horizontally. Each token has some number written on it.

Ninja wants to count the longest subsequence of the tokens with a “Zig-Zag” arrangement.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Note : 
A “Zig-Zag” arrangement is an arrangement where the differences between successive numbers on tokens strictly alternate between positive and negative integers.

Example :

“3 8 5 9 4 7 2 6” is a “Zig-Zag” arrangement as the differences “5 -3 4 -5 3 -5 4” alternates between positive and negative.
Note : 
The first difference (if one exists) may be either positive or negative.

Your task is to help Ninja in finding the longest subsequence of “Zig-Zag” arrangement of tokens.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test case

The first line of each test case contains an integer ‘N’ denoting the number of tokens.

The second line of each test case contains ‘N’ space-separated integers denoting the numbers printed on each token.
Output Format : 
For each test case, print an integer representing the length of the longest “Zig-Zag” subsequence.

Print the output of each test case in a separate line.
Note : 
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 100
1 <= N <= 1000
0 <= X <= 1000

Where ‘X’ denotes the number printed on the token. 

Time Limit: 1 sec
Sample Input 1 :
2
8
3 8 5 9 4 7 2 6
4
5 8 4 2
Sample Output 1 :
8
3
Explanation for Sample Input 1 :
Case 1 :
The differences for the given array “3 8 5 9 4 7 2 6” is “5 -3 4 -5 3 -5 4”. Each difference is alternating between one positive and then a negative value, so the whole array contains the “Zig-Zag” subsequence. Therefore, the length of the longest Zig-Zag subsequence is 8.

Case 2 :
The differences for the given array “5 8 4 2” is “3 -4 -2”. Each difference is alternating between one positive and negative value till element ‘4’ in the array, so the longest “Zig-Zag” subsequence will contain the elements “5 8 4”. Therefore the length of the longest “Zig-Zag” subsequence is 3.
Sample Input 2 :
2
9
1 9 8 10 2 4 0 5 1
13
2 3 4 6 10 4 5 9 6 8 3 7 4
Sample Output 2 :
9
9
Hint

Can you think of finding every length of the zig-zag subsequence?

Approaches (4)
Recursive

We can find every length of the zig-zag arrangement and find the maximum length out of it.

 

We will use a recursive function, Solve (tokenArray, index, isIncreasing) which will take the array “tokenArray”, index “index”, and a Boolean variable “isIncreasing” which will tell us whether we need to find increasing “Zig-Zag” arrangement or decreasing “Zig-Zag” arrangement. 

 

If the function “Solve” is called after decreasing “Zig-Zag” arrangement then we will call the same function with increasing “Zig-Zag” arrangement and Vice-Versa.

 

Algorithm –

 

  • Create a recursive “Solve” function:
  • Initialise a variable “maxCounter” = 0, which will store the maximum increasing or decreasing arrangement.
  • Now iterate over the “tokenArray” from index ‘i’ = “index” + 1 to the length of the “tokenArray”.
  • Inside the iteration, if “isIncreasing” is true and the current iterative element of array is greater than the “index” element of the array OR if “isIncreasing” is false and the current iterative element of the array is smaller than the “index” element of the array then:
  • Store the maximum count in the “maxCounter” by calling the “Solve” function recursively for the rest elements and making the Boolean operator “isIncreasing” as False.
  • maxCounter = 1 + max (maxCounter, Solve (tokenArray, i, !isInc))
  • Return the “maxCounter”. 
  • Inside the main “ZigZagSubsequence” function:
    • If the length of the “arr” is less than 2 then we will be returning with the length of “tokenArray”.
    • If the length of “arr” is greater than 2 then we will be returning with maximum count of “Zig-Zag” arrangement by calling recursive function “Solve” first by making Boolean operator “isIncreasing” as True and then by making “isIncreasing” as False
      • maxCounter = 1 + max (Solve (tokenArray, 0, true), Solve (tokenArray,0, false)).
Time Complexity

O (N!) Where ‘N’ is the number of elements in the Array.

 

Since the “Solve” function will be called maximum N ! times, therefore the time complexity is O(N!)

Space Complexity

O(N), where ‘N’ denotes the number of elements in the tokenArray.

 

Since we are using a recursive stack of size N, the space complexity is O(N).

Code Solution
(100% EXP penalty)
Zig Zag Subsequence
Full screen
Console