New update is available. Click here to update.

Last Updated: 30 Nov, 2021

Moderate

```
Can you try to solve this problem in O(N) time without using extra space?
```

```
Kindly use print statements to debug the code and print array.
```

```
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.
```

```
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.
```

```
For each test case, print array elements after applying wiggle sort.
Output for each test case will be printed in a separate line.
```

```
You are not required to print anything; it has already been taken care of. Just implement the function.
```

```
1 ≤ T ≤ 10
1 ≤ N ≤ 5000
-10^9 ≤ ARR[i] ≤ 10^9
Time limit: 1 sec
```

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.

- 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’**.

- Insert the element corresponding to
- 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’**.

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.

- 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.

- If
- Finally, return the input array itself.