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

Problem of the day

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.

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

Detailed explanation

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

```
2
5
1 2 3 4 5
4
1 3 2 2
```

```
1 4 2 5 3
1 3 2 2
```

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

```
2
5
1 1 1 1 1
2
1 2
```

```
1 1 1 1 1
1 2
```