# Rearrange the array with alternate high and low elements

Given an array of integers, rearrange the array such that every second element of the array is greater than its left and right elements. Assume no duplicate elements are present in the array.

For example,

Input:  {1, 2, 3, 4, 5, 6, 7}
Output: {1, 3, 2, 5, 4, 7, 6}

Input:  {9, 6, 8, 3, 7}
Output: {6, 9, 3, 8, 7}

Input:  {6, 9, 2, 5, 1, 4}
Output: {6, 9, 2, 5, 1, 4}

A simple solution would be to sort the array in ascending order first. Then we take another auxiliary array and fill it with elements starting from the two end-points of the sorted array in alternate order. Below is the complete algorithm –

rearrangeArray (int arr[], int n)

1. Sort the array in ascending order.

2. Take two index variables i and j to that points to two end-points of the array
(i.e. i = 0 and j = n – 1)

3. Create an auxiliary array A[] & initialize an index k with 0

4. while (i < j)
A[k++] = arr[i++]
A[k++] = arr[j–]

5. print A[]

The Time complexity of this solution would be O(nlogn) .

An efficient solution doesn’t involve sorting the array or use of auxiliary space. We start from the second element of the array and increment index by 2 for each iteration of loop. If previous element is greater than the current element, we swap the elements. Similarly if next element is greater than the current element, we swap both elements. At the end of loop, we will get the desired array that satisfies given constraints.

## Java

Output:

6 9 3 8 7

The time complexity of above solution is O(n) and auxiliary space used by the program is O(1).

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
AllergicToBitches

Nice solution..

Guest
Tony Lee

The “faster” solution is flawed because it can’t solve sequence like 1,1,1,9,9

Guest
Meraj

The assumption is the absence of duplicate elements.

Guest
kamasa

is this solution correct?

Output is [1, 4, 2, 6, 5, 9, 8]

Guest