Home Â» Technical Interview Questions Â» Array Interview Questions Â» Rearrange given Array in Maximum Minimum Form

# Rearrange given Array in Maximum Minimum Form

In rearrange given array in maximum minimum form problem, we have given a sorted array containing N elements. Rearrange the given sorted array of positive integers, such that alternative elements are ith max and ith min. See below for the better understanding for rearrangement of elements-

Array[0] = maximum value of the array, Array[1] = minimum value of the array, Array[2] = second maximum value of the array, Array[3] = second minimum value of the array, Array[4] = 3rd maximum value of the arrayÂ  â€¦… and so on.

## Example

Input

7

arr[] = {1, 2, 3, 4, 5, 6, 7}

Output

arr[] = {7, 1, 6, 2, 5, 3, 4}

## Algorithm for Rearrange given Array in Maximum Minimum Form

1.Â Create an auxiliary dummy array to store the modified array.

2.Â Initialize low and high as the corner indices of the array.

3.Â For copying alternative max and min store a variable X and initialize True, if X = True we copy max value and if X = False we copy min value.

4. Run a loop to copy elements into the auxiliary array. After copying an element into the new array reverse the value of X.

5. If X is True copy element from the end and moves backward if X is False copy element from the front and moves forward.

6. Copy the auxiliary array into the given array.

7.Â Print the array, the elements will be rearranged.

READ  Generate all possible sorted arrays from alternate elements of two given sorted arrays

## C++ Program for Rearrange given Array in Maximum Minimum Form

```#include <bits/stdc++.h>
using namespace std;

//function to rearrange the given sorted array in maximum minimum form
void RearrangeMaxMin(int array[], int N)
{
int temp[N];//auxilary dummy array with all zeroes
for (int i=0; i<N; i++)
{
temp[i] = 0;
}
int low=0, high=N-1; // corner indices of the array
int X = true; // indication for which element should be copied
//copying elements into the temp array
//according to the given condition
for (int i=0; i<N; i++)
{
if(X)
{
temp[i] = array[high--];
}
else
{
temp[i] = array[low++];
}
X = !X;
}
for (int i=0; i<N; i++)
{
array[i] = temp[i];
}
}
//function to print the given array
int PrintArray(int array[],int N)
{
for (int i=0; i<N; i++)
{
cout << array[i] << " ";
}
}
// main function
int main()
{
int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int N = sizeof(array)/sizeof(array[0]);
cout << "Input array\n";
PrintArray(array,N);
RearrangeMaxMin(array,N);
cout << "\nOutput array\n";
PrintArray(array,N);
return 0;
}```
```Input array
1 2 3 4 5 6 7 8 9
Output array
9 1 8 2 7 3 6 4 5```

## Complexity Analysis for Rearrange given Array in Maximum Minimum Form

### Time Complexity

O(N) where n is the number of elements present in the given array. Here we use two pointer methods and which run at most n times. So, we can say the time complexity is linear in this case.

### Space Complexity

O(N) because we use an auxiliary array for storing the elements in the maximum and minimum form.

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions