Last Updated: 30 Nov, 2021

Wiggle Sort

Moderate

Asked in company

Solve now

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.

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

Solve now

Approaches

01 Approach

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 :

Sort the input array.
Initialize two pointers ‘low’ equal to 0, and ‘high’ equal to N - 1.
Initialize a new array ‘wiggleSeq’.
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’.
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’.
Finally, return the array ‘wiggleSeq’.

Solve now

02 Approach

A clever observation is that if we swap the current adjacent pair of elements to satisfy the wiggle sort condition then it won’t affect the answer for the array elements following the elements of this pair.

Therefore, we can simply iterate through the array elements, and swap the adjacent pair elements if they don’t satisfy the wiggle sort condition.

The steps are as follows :

Run a for loop for variable ‘i’ from 0 to N - 2, inside the loop:
- If ‘i’ is even and ARR[i] > ARR[i+1], then swap the elements.
- If ‘i’ is odd and ARR[i] < ARR[i+1], then swap the elements.
Finally, return the input array itself.

Solve now