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

AD Blocker Detected !

Advertisements help running this website for free.

To view the content please disable AdBlocker and refresh the page.

Wait !!!

You can Crack Technical Interviews of Companies like Amazon, Google, LinkedIn, Facebook, PayPal, Flipkart, etc

Anisha was able to crack Amazon after practicing questions from TutorialCup