Wiggle Sort

Moderate
0/80
profile
Contributed by
9 upvotes
Asked in companies
FacebookPICE

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 )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains a single integer ‘N’, denoting the length of the binary string(s).

The second line of each test case contains N distinct integers ‘ARR’, denoting the array elements of the array.
Output Format : 
For each test case, print array elements after applying wiggle sort.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
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
Hint

Try to greedily place the largest and smallest array element depending on the array index.

Approaches (2)
Sorting

A naive approach so that the property ARR[0] ≤ ARR[1] ≥ ARR[2] ≤ ARR[3] ≥ ARR[4] ≤ ARR[5] ….. is satisfied is to place the largest available element for ARR[1], ARR[3], ARR[5], so on, and place the smallest available element for ARR[0], ARR[2], and all other even indices.

 

To keep the track of largest and smallest available elements, we can sort the array and use two pointers that point to the largest and smallest element currently, if we place the smallest element then we can increment the value of the pointer and if we place the largest element then we can decrement the value of the corresponding pointer.

 

The steps are as follows :

  1. Sort the input array.
  2. Initialize two pointers ‘low’ equal to 0, and ‘high’ equal to N - 1.
  3. Initialize a new array ‘wiggleSeq’.
  4. Run a while loop till ‘low’ is less than ‘high’, inside the while loop:
    • Insert the element corresponding to ‘low’ in the array ‘wiggleSeq’.
    • Insert the element corresponding to ‘high’ in the array ‘wiggleSeq’.
    • Increment the value of ‘low’ and decrement the value of ‘high’.
  5. Check if ‘low’ equals ‘high’, this will be the case when ‘N’ has odd parity. In this case, insert the element corresponding to ‘low’ in the array ‘wiggleSeq’.
  6. Finally, return the array ‘wiggleSeq’.
Time Complexity

O( N * log ( N ) ), where N denotes the size of the array.

 

We sort the array which takes ~N*logN time. We then iterate over each array element exactly once.

Hence the time complexity is O( N*log(N) ).

Space Complexity

O( N ), where N denotes the size of the array.

 

Extra space is used to build the new wiggle sorted array containing N elements.

Hence the space complexity is O( N ).

Code Solution
(100% EXP penalty)
Wiggle Sort
Full screen
Console