Rearrange given Array in Maximum Minimum Form

Problem Statement

In the “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 a better understanding of 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

7
1 2 3 4 5 6 7

7 1 6 2 5 3 4

Algorithm

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.
4. If X = True we copy max value and if X = False we copy min value.
5. Run a loop to copy elements into the auxiliary array. After copying an element into the new array reverse the value of X.
6. If X is True copy element from the end and moves backward if X is False copy element from the front and moves forward.
7. Copy the auxiliary array into the given array.
8. Print the array, the elements will be rearranged.

Implementation

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

Java Program for Rearrange given Array in Maximum Minimum Form

import java.util.Scanner;
class sum
{
    //function to rearrange the given sorted array in maximum minimum form
    public static void RearrangeMaxMin(int array[], int N)
    {
        int temp[] = new int [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 = 1; // 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==1)
                {
                    temp[i] = array[high--];
                }
            else
                {
                    temp[i] = array[low++];
                }
            if(X==1)
            {
                X=0;
            }
            else
            {
                X=1;
            }
        }
        for (int i=0; i<N; i++)
         {
            array[i] = temp[i];
         }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        System.out.println("Input array");
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.println();
        RearrangeMaxMin(a,n);
        System.out.println("Output array");
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
        System.out.println();
    }
}

5
5 4 3 2 1

Input array
5 4 3 2 1 
Output array
1 5 2 4 3

Complexity Analysis

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 form of the maximum element and minimum element.

References