Home » Data Structure » Array Data Structure

Rearrange an Array in maximum minimum form with O(1) extra space

C++ implementation to rearrange an array in maximum minimum form with O(1) extra space.
Submitted by Vikneshwar GK, on March 16, 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. The condition here is that the solution must use an auxiliary array.

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:

This method uses multiplication and modular division to rearrange the elements in the array. It uses two pointers min and max to hold the index of minimum and maximum elements. It involves the following steps:

Assign min = 0, and max = n-1 where n is the length of the array.
Initialize maxVal = array[n-1] + 1, which is used in the multiplication and modular division.
Iterate through the array.
If the index is even, perform modular division by maxVal to the element at the max position and multiply it with maxVal. Add the resultant to the current array element. Decrement the max pointer.
If the index is odd, perform modular division by maxVal to the element at the min position and multiply it with maxVal. Add the resultant to the current array element. Increment the min pointer.
To bring the array back to its original form, iterate through the array and divide every element by maxVal.
Print the array.

C++ Implementation:

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

void rearrangeArray(int array[], int length)
{
    // min max pointers
    int max = length - 1, min = 0;

    // store maximum element of array
    int maxVal = array[length - 1] + 1;

    // iterate through the array
    for (int i = 0; i < length; i++) {
        // if even, store the max element
        if (i % 2 == 0) {
            array[i] += (array[max] % maxVal) * maxVal;
            max--;
        }
        // id odd, store the min element
        else {
            array[i] += (array[min] % maxVal) * maxVal;
            min++;
        }
    }

    // array elements back to it's original form
    for (int i = 0; i < length; i++)
        array[i] = array[i] / maxVal;
}

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

// Main function
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);
    printArray(array, N);

    return 0;
}

Output:

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

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