Home » Data Structure » Array Data Structure

Rearrange an array in maximum minimum form

C++ implementation to rearrange an array in maximum minimum form.
Submitted by Vikneshwar GK, on March 15, 2022

Consider a sorted integer array, of size n. The task at hand is to arrange the array in such a way that the maximum element is placed in 0^th position, minimum element is placed in 1^st position, 2^nd maximum element at 3^rd position, 2^nd minimum element at 4^th position, and so on.

Example:

Input:
array[]= {1, 2, 3, 4, 5, 6}

Output:
array[] = {6, 1, 5, 2, 4, 3} 
Explanation:

1st max element = 6
1st min element = 1
2nd max element = 5
2nd min element = 2
and so on...

Input:
array[] = {5, 10, 15, 20, 25, 30}

Output:
array[] = {30, 5, 25, 10, 20, 15}

Solution:

One of the simple solutions is to use an auxiliary array to store the required arrangement of the array. Since the original array is sorted, we use min-max pointers to store the maximum and minimum elements in the auxiliary array, accordingly.

Set min = 0, and max = n-1, where n is the length of the array
Iterate through the original array.
If the index is even, place the max pointer element in the auxiliary array and decrement the pointer.
If the index is odd, place the min pointer element in the auxiliary array and increment the pointer
Finally, print the array.

C++ Implementation:

#include <iostream>
using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

void rearrangeArray(int array[], int length){
    // temporary array to hold the rearranged array
    int temp[length];

    // min-max pointers to hold minimum and maximum elements
    int min = 0, max = length - 1;

    // iterate through the array
    for (int i = 0; i < length; i++) {
        // to store maximum elements
        if (i % 2 == 0)
            temp[i] = array[max--];
        // to store minimum elements
        else
            temp[i] = array[min++];
    }

    printArray(temp, length);
}

// Driver program
int main()
{
    int array[100];
    int N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    rearrangeArray(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1: 1
Enter element 2: 2
Enter element 3: 3
Enter element 4: 4
Enter element 5: 5
Enter element 6: 6
6 1 5 2 4 3

Time Complexity: O(n), where n is the length of the array.