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

Try it on GfG Practice

Given a sorted array of positive integers, rearrange the array alternately i.e first element should be the maximum value, second minimum value, third-second max, fourth-second min and so on. 

Examples:

Input: arr[] = {1, 2, 3, 4, 5, 6, 7} 
Output: arr[] = {7, 1, 6, 2, 5, 3, 4}
Explanation: First 7 is the max value, then 1 is the min value, then 6 is the second max value, then 2 is the second min value, then 5 is the third max value, then 3 is the third min value and at last 4 is the fourth max value.

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

Rearrange an array in maximum minimum form using modular arithmetic:

The idea is to use multiplication and modular arithmetic to store two elements at each index. Assume M = maximum element in the array + 1. Now, if we want to store two numbers say X and Y at any index, then we can store X + (Y * M) at that index. This will work because using X + (Y * M), we can get the first value by using modulo: (X + (Y * M)) mod M = X and the second value by using (X + (Y * M)) / M = Y.

To arrange the elements alternately, we can maintain two pointers min_idx = 0 to keep track of the next minimum element and max_idx = N – 1 to keep track of next maximum element. Now, iterate from i = 0 to N – 1,

• If i is even, then we need to place maximum remaining element, so update arr[i] = arr[i] + (arr[max_idx] % M) * M and decrement max_idx by 1. Now, arr[i] has arr[i] as well as arr[max_idx] as its value.
• If i is odd, then we need to place minimum remaining element, so update arr[i] = arr[i] + (arr[min_idx] % M) * M and increment min_idx by 1. Now, arr[i] has arr[i] as well as arr[min_idx] as its value.

Finally, again iterate from i = 0 to N – 1 and update arr[i] = arr[i] / M.

Below is the implementation of the algorithm:

// C++ program to rearrange an array in minimum
// maximum form

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

// Function to rearrange array alternately
void rearrange(long long* arr, int n)
{
    // initialize index of first minimum and first
    // maximum element
    int max_idx = n - 1, min_idx = 0;

    // store maximum element of array
    long long M = arr[n - 1] + 1;

    // traverse array elements
    for (int i = 0; i < n; i++) {
        // at even index : we have to put maximum element
        if (i % 2 == 0) {
            arr[i] += (arr[max_idx] % M) * M;
            max_idx--;
        }

        // at odd index : we have to put minimum element
        else {
            arr[i] += (arr[min_idx] % M) * M;
            min_idx++;
        }
    }

    // Reduce array elements to store the new value
    for (int i = 0; i < n; i++)
        arr[i] = arr[i] / M;
}

// Driver program to test above function
int main()
{
    long long arr[] = { 1, 2, 3, 4, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original Array\n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";

    rearrange(arr, n);

    cout << "\nModified Array\n";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

// Java program to rearrange an array in minimum maximum
// form

public class Main {

    // Function to rearrange array alternately
    public static void rearrange(long[] arr, int n)
    {
        // Initialize index of first minimum and first
        // maximum element
        int maxIdx = n - 1, minIdx = 0;

        // Store maximum element of array
        long M = arr[n - 1] + 1;

        // Traverse array elements
        for (int i = 0; i < n; i++) {
            // At even index : we have to put maximum
            // element
            if (i % 2 == 0) {
                arr[i] += (arr[maxIdx] % M) * M;
                maxIdx--;
            }
            // At odd index : we have to put minimum element
            else {
                arr[i] += (arr[minIdx] % M) * M;
                minIdx++;
            }
        }

        // Reduce array elements to store the new value
        for (int i = 0; i < n; i++) {
            arr[i] = arr[i] / M;
        }
    }

    // Driver code
    public static void main(String args[])
    {
        long[] arr = { 1, 2, 3, 4, 5, 6 };
        int n = arr.length;

        System.out.println("Original Array");
        for (long num : arr) {
            System.out.print(num + " ");
        }

        rearrange(arr, n);

        System.out.println("\nModified Array");
        for (long num : arr) {
            System.out.print(num + " ");
        }
    }
}

# Python3 program to rearrange an
# array in minimum maximum form

# Function to rearrange array alternately
def rearrange(arr, n):

    # Initialize index of first minimum and first maximum element
    max_idx = n - 1
    min_idx = 0

    # Store maximum element of array
    M = arr[n - 1] + 1

    # Traverse array elements
    for i in range(n):
        # At even index : we have to put maximum element
        if i % 2 == 0:
            arr[i] += (arr[max_idx] % M) * M
            max_idx -= 1
        # At odd index : we have to put minimum element
        else:
            arr[i] += (arr[min_idx] % M) * M
            min_idx += 1

    # Reduce array elements to store the new value
    for i in range(n):
        arr[i] = arr[i] // M


# Driver Code
arr = [1, 2, 3, 4, 5, 6]
n = len(arr)

print("Original Array")
for i in range(n):
	print(arr[i], end=" ")

rearrange(arr, n)

print("\nModified Array")
for i in range(n):
	print(arr[i], end=" ")

// C# program to rearrange an
// array in minimum maximum form
using System;

class main {

    // Function to rearrange array alternately
    static void rearrange(long[] arr, int n)
    {
        // Initialize index of first minimum and first
        // maximum element
        int maxIdx = n - 1, minIdx = 0;

        // Store maximum element of array
        long M = arr[n - 1] + 1;

        // Traverse array elements
        for (int i = 0; i < n; i++) {
            // At even index : we have to put maximum
            // element
            if (i % 2 == 0) {
                arr[i] += (arr[maxIdx] % M) * M;
                maxIdx--;
            }
            // At odd index : we have to put minimum element
            else {
                arr[i] += (arr[minIdx] % M) * M;
                minIdx++;
            }
        }

        // Reduce array elements to store the new value
        for (int i = 0; i < n; i++) {
            arr[i] = arr[i] / M;
        }
    }

    // Driver code
    public static void Main()
    {
        long[] arr = { 1, 2, 3, 4, 5, 6 };
        int n = arr.Length;
        Console.WriteLine("Original Array");
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();

        rearrange(arr, n);

        Console.WriteLine("Modified Array");
        for (int i = 0; i < n; i++)
            Console.Write(arr[i] + " ");
    }
}

// JavaScript program to rearrange an array in minimum 
// maximum form 

// Function to rearrange array alternately
function rearrange(arr, n) {
    // initialize index of first minimum and first maximum element
    let max_idx = n - 1, min_idx = 0;

    // store maximum element of array
    let M = arr[n - 1] + 1;

    // traverse array elements
    for (let i = 0; i < n; i++) {
        // at even index : we have to put maximum element
        if (i % 2 == 0) {
            arr[i] += (arr[max_idx] % M) * M;
            max_idx--;
        }
        // at odd index : we have to put minimum element
        else {
            arr[i] += (arr[min_idx] % M) * M;
            min_idx++;
        }
    }

    // Reduce array elements to store the new value
    for (let i = 0; i < n; i++) {
        arr[i] = Math.floor(arr[i] / M);
    }
}

// Driver code to test above function
let arr = [1, 2, 3, 4, 5, 6];
let n = arr.length;

console.log("Original Array");
console.log(arr.join(" "));

rearrange(arr, n);

console.log("Modified Array");
console.log(arr.join(" "));

<?php
// PHP program to rearrange an 
// array in minimum-maximum form

// Function to rearrange array alternately
function rearrange(&$arr, $n) {
    // initialize index of first minimum and first maximum element
    $max_idx = $n - 1;
    $min_idx = 0;

    // store maximum element of array
    $M = $arr[$n - 1] + 1;

    // traverse array elements
    for ($i = 0; $i < $n; $i++) {
        // at even index : we have to put maximum element
        if ($i % 2 == 0) {
            $arr[$i] += ($arr[$max_idx] % $M) * $M;
            $max_idx--;
        }
        // at odd index : we have to put minimum element
        else {
            $arr[$i] += ($arr[$min_idx] % $M) * $M;
            $min_idx++;
        }
    }

    // Reduce array elements to store the new value
    for ($i = 0; $i < $n; $i++) {
        $arr[$i] = intdiv($arr[$i], $M);
    }
}

// Driver code to test above function
$arr = array(1, 2, 3, 4, 5, 6);
$n = count($arr);

echo "Original Array\n";
for ($i = 0; $i < $n; $i++) {
    echo $arr[$i] . " ";
}
echo "\n";

rearrange($arr, $n);

echo "Modified Array\n";
for ($i = 0; $i < $n; $i++) {
    echo $arr[$i] . " ";
}
echo "\n";

?>

Original Array
1 2 3 4 5 6 
Modified Array
6 1 5 2 4 3 

Working of the above algorithm:

Complexity Analysis:

• Time Complexity: O(N), where N is the size of input array arr[]
• Auxiliary Space: O(1), as no extra space is used

Related Articles:

• Rearrange an array in maximum minimum form using Two Pointers