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.