Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Wiggle Sort

Moderate
0/80
profile
Contributed by
8 upvotes
Asked in company
Facebook

Problem statement

You are given an array ‘ARR’ containing ‘N’ integers, you need to sort the array such that a wiggle sequence is formed. A wiggle sequence satisfies the following property: ARR[0] ≤ ARR[1] ≥ ARR[2] ≤ ARR[3] ≥ ARR[4] ≤ ARR[5] …..

If there are multiple answers, you may print any of them.

Follow up :
Can you try to solve this problem in O(N) time without using extra space?
Custom Input :
Kindly use print statements to debug the code and print array.
Example :
If ‘N’ = 5 and ‘ARR’ = { 1, 2, 3, 4, 5 }

Then rearranging the input array to { 1, 4, 2, 5, 3 } create a wiggle sequence.

Other rearrangements like { 2, 4, 3, 5, 1 }, { 3, 5, 1, 4, 2} are also considered correct.
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
1 ≤ T ≤ 10      
1 ≤ N ≤ 5000
-10^9 ≤ ARR[i] ≤ 10^9

Time limit: 1 sec
Sample Input 1 :
2
5
1 2 3 4 5
4
1 3 2 2 
Sample Output 1 :
1 4 2 5 3
1 3 2 2
Explanation For Sample Input 1 :
For test case 1 :
We will print {1, 4, 2, 5, 3} as it is a valid rearrangement of the input array and is a wiggle sequence.

For test case 2 : 
The input array is itself a wiggle sequence, so we can directly return it.
Sample Input 2 :
2
5
1 1 1 1 1
2
1 2 
Sample Output 2 :
1 1 1 1 1
1 2
Full screen
Console