Print array as first element is first maximum and second element is first minimum and so on

By | October 29, 2023
0 Comment

Given an array of unique integers, print the array in such a way that the first element is first maximum and second element is first minimum and so on. We have to Rearrange an array in maximum minimum form using Two Pointer Technique.

Examples:

Input : arr[] = {7, 1, 2, 3, 4, 5, 6}
Output : 7 1 6 2 5 3 4

Input : arr[] = {1, 6, 9, 4, 3, 7, 8, 2}
Output : 9 1 8 2 7 3 6 4

RECOMMENDED: Find the Minimum element in a Sorted and Rotated Array

Approach:
There is exist a solution with O(n log n) time complexity.

Method using counting sort :

1) Maintain a new array keeping track of count.
2) Take two pointers, one at the beginning of array and other at the end.
Now, print the elements alternatively from both sides of array and
move the pointers towards each other.

Below is the C++ implementation using Counting Sort.

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

// Function to print the array with first maximum and then first minimum
void alternateSort(int arr[], int n) {
    sort(arr, arr + n); // Sort the array in ascending order

    int left = 0, right = n - 1;

    while (left < right) {
        cout << arr[right] << " " << arr[left] << " ";
        left++;
        right--;
    }

    // If there's an odd number of elements, print the middle element
    if (left == right) {
        cout << arr[left] << " ";
    }
}

int main() {
    int arr1[] = {7, 1, 2, 3, 4, 5, 6};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);

    cout << "Output for arr1: ";
    alternateSort(arr1, n1);
    cout << endl;

    int arr2[] = {1, 6, 9, 4, 3, 7, 8, 2};
    int n2 = sizeof(arr2) / sizeof(arr2[0);

    cout << "Output for arr2: ";
    alternateSort(arr2, n2);
    cout << endl;

    return 0;
}

Output:

Output for arr1: 7 1 6 2 5 3 4 
Output for arr2: 9 1 8 2 7 3 6 4

Time complexity : O(nlogn)
Space complexity : O(n)

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.

Related Posts