×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

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 0th position, minimum element is placed in 1st position, 2nd maximum element at 3rd position, 2nd minimum element at 4th 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.


Related Tutorials



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.