Hello Everyone,

Given an array, rearrange the array such that :

- If index i is even, arr[i] <= arr[i+1]
- If index i is odd, arr[i] >= arr[i+1]

**Note :** There can be multiple answers.

**Examples:**

**Input :** arr[] = {2, 3, 4, 5}

**Output :** arr[] = {2, 4, 3, 5}

Explanation : Elements at even indexes are smaller and elements at odd indexes are greater than their next elements

**Note :** Another valid answer is arr[] = {3, 4, 2, 5} Input :arr[] = {6, 4, 2, 1, 8, 3} Output :arr[] = {4, 6, 1, 8, 2, 3}

This problem is similar to sort an array in wave form.

A **simple solution** is to sort the array in decreasing order, then starting from second element, swap the adjacent elements.

An **efficient solution** is to iterate over the array and swap the elements as per the given condition.

If we have an array of length n, then we iterate from index 0 to n-2 and check the given condition.

At any point of time if i is even and arr[i] > arr[i+1], then we swap arr[i] and arr[i+1]. Similarly, if i is odd and

arr[i] < arr[i+1], then we swap arr[i] and arr[i+1].

For the given example:

Before rearrange, arr[] = {2, 3, 4, 5}

Start iterating over the array till index 2 (as n = 4)

First Step:

At i = 0, arr[i] = 2 and arr[i+1] = 3. As i is even and arr[i] < arr[i+1], don’t need to swap.

Second step:

At i = 1, arr[i] = 3 and arr[i+1] = 4. As i is odd and arr[i] < arr[i+1], swap them.

Now arr[] = {2, 4, 3, 5}

Third step:

At i = 2, arr[i] = 3 and arr[i+1] = 5. So, don’t need to swap them

After rearrange, arr[] = {2, 4, 3, 5}

`// CPP code to rearrange an array such that`

`// even index elements are smaller and odd`

`// index elements are greater than their`

`// next.`

`#include <iostream>`

`using`

`namespace`

`std;`

`void`

`rearrange(`

`int`

`* arr, `

`int`

`n)`

`{`

` `

`for`

`(`

`int`

`i = 0; i < n - 1; i++) {`

` `

`if`

`(i % 2 == 0 && arr[i] > arr[i + 1])`

` `

`swap(arr[i], arr[i + 1]);`

` `

`if`

`(i % 2 != 0 && arr[i] < arr[i + 1])`

` `

`swap(arr[i], arr[i + 1]);`

` `

`}`

`}`

`/* Utility that prints out an array in`

` `

`a line */`

`void`

`printArray(`

`int`

`arr[], `

`int`

`size)`

`{`

` `

`for`

`(`

`int`

`i = 0; i < size; i++)`

` `

`cout << arr[i] << `

`" "`

`;`

` `

`cout << endl;`

`}`

`/* Driver function to test above functions */`

`int`

`main()`

`{`

` `

`int`

`arr[] = { 6, 4, 2, 1, 8, 3 };`

` `

`int`

`n = `

`sizeof`

`(arr) / `

`sizeof`

`(arr[0]);`

` `

`cout << `

`"Before rearranging: \n"`

`;`

` `

`printArray(arr, n);`

` `

`rearrange(arr, n);`

` `

`cout << `

`"After rearranging: \n"`

`;`

` `

`printArray(arr, n);`

` `

`return`

`0;`

`}`

**Output:**

Before rearranging: 6 4 2 1 8 3 After rearranging: 4 6 1 8 2 3

**Time Complexity :** O(n)

**Auxiliary Space:** O(1)