Rearrange an array in maximum minimum form

By | October 6, 2021

You are given a sorted array as the input. You have to rearrange the array in such a manner that all the elements represent the maximum-minimum form at alternative indices. For example, the first element would be the maximum element, the second element would be the minimum element. The third element would be the next maximum element, the fourth element would be the next minimum element, and so on.

In the following article, we will be learning approaches to solve the following problem: The first approach will take O(n) time, while the other approach will be more optimized and solve this problem in O(log n) time.

Vamware

Example 1: 

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

Explanation: In this example, if you closely observe the first element of the output array that is 7, is the largest element of the input element. Then, the second element of the output array which is 1, is the smallest element of the input array. Similarly third and fourth elements of the input array i.e., 6 and 2 are the next maximum and minimum elements of the input array respectively. So is the fifth and sixth element that is 5 and 3 respectively. And at the end, 4 is the remaining element of the input array. Hence we get the output {7, 1, 6, 2, 5, 3, 4}.

Example 2: 

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

Explanation: Just like the earlier example, if we look at the input array, 6 is the maximum array while 1 is the smallest array. So we get the maximum-minimum form at the first two indices of the output array. A similar pattern can be observed throughout the entire output array.

Approach 1: 

This approach takes O(n) time for solving this problem. The idea is simple. We will be using an additional empty array of size n, where n is the number of elements of the input array. We will manage two pointers, one at the starting index of the input array and another one at the endpoint. We will copy the last element of the array first, in the additional array, then the first element of the array, and increment both the pointers one index further, We will be following the same pattern unless the start pointer becomes less than or equal to the end pointer.

Algorithm

  1. Create an array to store a rearranged array.
  2. Initialize the indices of the first max and first min elements as 0 and n-1 where n is the number of elements of the array respectively.
  3. Create a flag element that will be initially true to indicate if there are remaining elements to be copied.
  4. Store the rearranged values in the temp array.
  5. Copy the elements of the temp array.
  6. Return the output array.

The implementation of the above-discussed approach is:

CPP

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

// function to rearrange the given array 
// in maximum minimum form, 
// using an auxiliary array.
void minMaxArray(int arr[], int n)
{
	// array to store rearranged array
	int temp[n];

	// initialize the indices
	// of the first max and first min elements
	int small = 0, large = n - 1;

	// flag to indicate if there are
	// remaining elements to be copied
	int flag = true;

	// store the rearranged values in
	// the temp array
	for (int i = 0; i < n; i++) {
		if (flag)
			temp[i] = arr[large--];
		else
			temp[i] = arr[small++];

		flag = !flag;
	}

	// finally copy the elements of
	// the temp array
	// to the original array
	for (int i = 0; i < n; i++)
		arr[i] = temp[i];
}

// Driver code
int main()
{
	int arr[] = { 1, 2, 3, 4, 5, 6 };
	int n = sizeof(arr) / sizeof(arr[0]);

	minMaxArray(arr, n);

	cout << "The rearranged array is:\n";
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	cout << "\n\n";
	return 0;
}

Output

The rearranged array is:
6 1 5 2 4 3 

JAVA

import java.util.Arrays;

public class Main
{
	// function to rearrange the given array 
	// in maximum minimum form, 
	// using an auxiliary array.
	static void minMaxArray(int[] arr, int n)
	{
		// array to store rearranged array
		int temp[] = arr.clone();

		// intitlaize the indices
		// of the first max and first min elements
		int small = 0, large = n - 1;

		// flag to indicate if there are
		// remaining elements to be copied
		boolean flag = true;

		// store the rearranged values in
		// the temp array
		for (int i = 0; i < n; i++) {
			if (flag)
				arr[i] = temp[large--];
			else
				arr[i] = temp[small++];

			flag = !flag;
		}
	}

	public static void main(String[] args)
	{
		int arr[] = new int[] { 1, 2, 3, 4, 5, 6 };

		minMaxArray(arr, arr.length);

		System.out.println("The rearranged array is:");
		System.out.println(Arrays.toString(arr));
		System.out.print("\n\n");
	}
}

Output

The rearranged array is:
[6, 1, 5, 2, 4, 3]

Python

# function to rearrange the given array 
# in maximum-minimum form, 
# using an auxiliary array.

def minMaxArray(arr, n):
	# array to store rearranged array
	temp = n*[None]

	# intitlaize the indices
	# of the first max and first min elements
	small, large = 0, n-1

	# flag to indicate if there are
	# remaining elements to be copied
	flag = True

	# store the rearranged values in
	# the temp array
	for i in range(n):
		if flag is True:
			temp[i] = arr[large]
			large -= 1
		else:
			temp[i] = arr[small]
			small += 1

		flag = bool(1-flag)

	# finally copy the elements of
	# the temp array
	# to the original array
	for i in range(n):
		arr[i] = temp[i]
	return arr


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

print("The rearranged array is:")
print(minMaxArray(arr, n))
print("\n")

Output

The rearranged array is:
[6, 1, 5, 2, 4, 3]

C#

using System;

class main {

	// function to rearrange the given array 
	// in maximum minimum form, 
	// using an auxiliary array.
	static void minMAxArray(int[] arr, int n)
	{
		// array to store rearranged array
		int[] temp = new int[n];

		// intitlaize the indices
		// of the first max and first min elements
		int small = 0, large = n - 1;

		// flag to indicate if there are
		// remaining elements to be copied
		bool flag = true;

		// store the rearranged values in
		// the temp array
		for (int i = 0; i < n; i++) {
			if (flag)
				temp[i] = arr[large--];
			else
				temp[i] = arr[small++];

			flag = !flag;
		}

		// finally copy the elements of
		// the temp array
		// to the original array
		for (int i = 0; i < n; i++)
			arr[i] = temp[i];
	}

	// Driver Code
	static void Main()
	{
		int[] arr = { 1, 2, 3, 4, 5, 6 };

		minMAxArray(arr, arr.Length);

		Console.WriteLine("The rearranged array is:");
		for (int i = 0; i < arr.Length; i++)
			Console.Write(arr[i] + " ");
		Console.Write("\n\n");
	}
}

Output

The rearranged array is:
6 1 5 2 4 3

PHP

<?php
// function to rearrange the given array 
// in maximum minimum form, 
// using an auxiliary array.
function minMaxArray(&$arr, $n)
{
	// array to store rearranged array
	$temp = array();

	// intitlaize the indices
	// of the first max and first min elements
	$small = 0;
	$large = $n - 1;

	// flag to indicate if there are
	// remaining elements to be copied
	$flag = true;

	// store the rearranged values in
	// the temp array
	for ($i = 0; $i < $n; $i++)
	{
		if ($flag)
			$temp[$i] = $arr[$large--];
		else
			$temp[$i] = $arr[$small++];

		$flag = !$flag;
	}

	// finally copy the elements of
	// the temp array
	// to the original array
	for ($i = 0; $i < $n; $i++)
		$arr[$i] = $temp[$i];
}

// Driver Code
$arr = array(1, 2, 3, 4, 5, 6);
$n = count($arr);

minMaxArray($arr, $n);

echo "The rearranged array is:\n";
for ($i = 0; $i < $n; $i++) echo $arr[$i] . " "; echo "\n\n" ?>

Output

The rearranged array is:
6 1 5 2 4 3

JavaScript

// function to rearrange the given array 
// in maximum minimum form, 
// using an auxiliary array.
function minMaxArray(arr, n)
{
    // array to store rearranged array
    let temp = new Array(n);

    // intitlaize the indices
    // of the first max and first min elements
    let small = 0, large = n - 1;

    // flag to indicate if there are
    // remaining elements to be copied
    let flag = true;

    // store the rearranged values in
    // the temp array
    for (let i = 0; i < n; i++) {
        if (flag)
            temp[i] = arr[large--];
        else
            temp[i] = arr[small++];

        flag = !flag;
    }

    // finally copy the elements of
    // the temp array
    // to the original array
    for (let i = 0; i < n; i++)
        arr[i] = temp[i];
}

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

    minMaxArray(arr, n);

    document.write("The rearranged array is:
");
    for (let i = 0; i < n; i++)
        document.write(arr[i] + " ");
    document.write("<br>");

Output

The rearranged array is:
6 1 5 2 4 3

Complexity Analysis

  • Time complexity: O(n), where n is the number of elements of the input array. This is because we are simply applying linear iteration over the input array and copying the elements in the output array.
  • Space complexity: O(n), where n is the number of elements of the input array. This is because we are using an additional array of size n to store the array elements.

Approach 2

This is the optimized solution to solve this problem. This approach will take O(1) space to solve the problem, as, unlike the above approach, we will not be using an auxiliary array. We will be using multiple modular tricks to rearrange the elements. The arrangement will be in place i.e., the elements will be rearranged within the input array. We will initialize the indices of the first max and first min elements as 0 and n-1 where n is the number of elements of the array respectively. Then, we will iterate over the input array and store the maximum elements in a decreasing order at even places, Similarly, we will store the minimum elements of the input array in increasing order at odd places. The array thus obtained will be the output array.

Algorithm

  1. Initialize the indices of the first max and first min elements as 0 and n-1 where n is the number of elements of the array respectively.
  2. Initialize the array’s maximum element.
  3. Iterate over the array and store max elements in a decreasing order at even indices.
  4. Store the min elements in increasing order at odd indices.
  5. Storing elements of the array in their original way.
  6. Return the array.

The implementation of the above-discussed approach is:

CPP

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

// function to rearrange the given array 
// in maximum minimum form, 
// without using an auxiliary array.
void minMaxArray(int arr[], int n)
{
	// intitlaize the indices
	// of the first max and first min elements
	int max_idx = n - 1, min_idx = 0;

	// intialize the array's maximum element
	int max_elem = arr[n - 1] + 1;

	// iterate over the array
	for (int i = 0; i < n; i++) {
		// store max elements at the even indices
		if (i % 2 == 0) {
			arr[i] += (arr[max_idx] % max_elem) * max_elem;
			max_idx--;
		}

		// store min elements at the odd indices
		else {
			arr[i] += (arr[min_idx] % max_elem) * max_elem;
			min_idx++;
		}
	}

	// storing elements of the array
	// in their original way
	for (int i = 0; i < n; i++)
		arr[i] = arr[i] / max_elem;
}

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

	minMaxArray(arr, n);

	cout << "The rearranged array is:\n";
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	
	cout << "\n\n";
	return 0;
}

Output

The rearranged array is:
6 1 5 2 4 3

JAVA

public class Main {

	// function to rearrange the given array 
	// in maximum minimum form, 
	// without using an auxiliary array.
	public static void minMaxArray(int arr[], int n)
	{
		// intitlaize the indices
		// of the first max and first min elements
		int max_idx = n - 1, min_idx = 0;

		// intialize the array's maximum element
		int max_elem = arr[n - 1] + 1;

		// iterate over the array
		for (int i = 0; i < n; i++) {
			// store max elements at the even indices
			if (i % 2 == 0) {
				arr[i] += (arr[max_idx] % max_elem) * max_elem;
				max_idx--;
			}

			// store min elements at the odd indices
			else {
				arr[i] += (arr[min_idx] % max_elem) * max_elem;
				min_idx++;
			}
		}

		// storing elements of the array
		// in their original way
		for (int i = 0; i < n; i++)
			arr[i] = arr[i] / max_elem;
	}

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

		minMaxArray(arr, n);

		System.out.print("The rearranged array is:\n");
		for (int i = 0; i < n; i++)
			System.out.print(arr[i] + " ");
		
		System.out.print("\n");
	}
}

Output

The rearranged array is:
6 1 5 2 4 3

Python

# function to rearrange the given array 
# in maximum minimum form, 
# without using an auxiliary array.
def minMaxArray(arr, n):

	# intitlaize the indices
	# of the first max and first min elements
	max_idx = n - 1
	min_idx = 0

	# intialize the array's maximum element
	max_elem = arr[n-1] + 1

	# iterate over the array
	for i in range(0, n) :

		# store max elements at the even indices
		if i % 2 == 0 :
			arr[i] += (arr[max_idx] % max_elem ) * max_elem
			max_idx -= 1

		# store min elements at the odd indices
		else :
			arr[i] += (arr[min_idx] % max_elem ) * max_elem
			min_idx += 1

	# storing elements of the array
	# in their original way
	for i in range(0, n) :
		arr[i] = arr[i] / max_elem


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

print ("The rearranged array is:")
for i in range(0, n):
	print (int(arr[i]), end = " ")
print("\n")

Output

The rearranged array is:
6 1 5 2 4 3

C#

using System;

class main {

	// function to rearrange the given array 
	// in maximum minimum form, 
	// without using an auxiliary array.
	public static void minMaxArray(int[] arr, int n)
	{
		// intitlaize the indices
		// of the first max and first min elements
		int max_idx = n - 1, min_idx = 0;

		// intialize the array's maximum element
		int max_elem = arr[n - 1] + 1;

		// iterate over the array
		for (int i = 0; i < n; i++) {

			// store max elements at the even indices
			if (i % 2 == 0) {
				arr[i] += (arr[max_idx] % max_elem) * max_elem;
				max_idx--;
			}

			// store min elements at the odd indices
			else {
				arr[i] += (arr[min_idx] % max_elem) * max_elem;
				min_idx++;
			}
		}

		// storing elements of the array
		// in their original way
		for (int i = 0; i < n; i++)
			arr[i] = arr[i] / max_elem;
	}

	// Driver code
	public static void Main()
	{
		int[] arr = { 1, 2, 3, 4, 5, 6 };
		int n = arr.Length;

		minMaxArray(arr, n);

		Console.WriteLine("The rearranged array is:");
		for (int i = 0; i < n; i++)
			Console.Write(arr[i] + " ");
		Console.Write("\n\n");
	}
}

Output

The rearranged array is:
6 1 5 2 4 3

PHP

<?php
// function to rearrange the given array 
// in maximum minimum form, 
// without using an auxiliary array.
function minMaxArray(&$arr, $n)
{
	// intitlaize the indices
	// of the first max and first min elements
	$max_idx = $n - 1; $min_idx = 0;

	// intialize the array's maximum element
	$max_elem = $arr[$n - 1] + 1;

	// iterate over the array
	for ($i = 0; $i < $n; $i++)
	{
		// store max elements at the even indices
		if ($i % 2 == 0)
		{
			$arr[$i] += ($arr[$max_idx] %
						$max_elem) * $max_elem;
			$max_idx--;
		}

		// store min elements at the odd indices
		else
		{
			$arr[$i] += ($arr[$min_idx] %
						$max_elem) * $max_elem;
			$min_idx++;
		}
	}

	// storing elements of the array
	// in their original way
	for ($i = 0; $i < $n; $i++)
		$arr[$i] = (int)($arr[$i] / $max_elem);
}

// Driver Code
$arr = array(1, 2, 3, 4, 5, 6);
$n = sizeof($arr);

minMaxArray($arr, $n);

echo "The rearranged array is:\n";
for ($i = 0; $i < $n; $i++) echo $arr[$i] . " "; echo "\n\n"; ?>

Output

The rearranged array is:
6 1 5 2 4 3

JavaScript

// function to rearrange the given array 
// in maximum minimum form, 
// using an auxiliary array.
function minMaxArray(arr, n)
{
	// intitlaize the indices
	// of the first max and first min elements
	let max_idx = n - 1, min_idx = 0;

	// intialize the array's maximum element
	let max_elem = arr[n - 1] + 1;

	// iterate over the array
	for (let i = 0; i < n; i++) {
		// store max elements at the even indices
		if (i % 2 == 0) {
			arr[i] += (arr[max_idx] % max_elem) * max_elem;
			max_idx--;
		}

		// store min elements at the odd indices
		else {
			arr[i] += (arr[min_idx] % max_elem) * max_elem;
			min_idx++;
		}
	}

	// storing elements of the array
	// in their original way
	for (let i = 0; i < n; i++)
		arr[i] = Math.floor(arr[i] / max_elem);
}

// Driver program 

	let arr = [ 1, 2, 3, 4, 5, 6 ];
	let n = arr.length;

	minMaxArray(arr, n);

	document.write("The rearranged array is:
");
	for (let i = 0; i < n; i++)
		document.write(arr[i] + " ");

    document.write("<br>");

Output

The rearranged array is:
6 1 5 2 4 3

Complexity Analysis

Time complexity: O(n), where n is the number of elements of the input array. This is because we are simply applying linear iteration over the input array and rearranging the elements with the same array.

Space complexity: O(1), where n will be the number of elements of the input array. This is so as, unlike the previous approach, we are not using an auxiliary array to store the array elements. We are rearranging the elements within the same array.. 

Wrapping Up!

In this article, we have learned an amazing as well as easy concept. Rearranging an array in the maximum-minimum form array is one of the most important data structures and is usually asked in the top interview questions as well.

In this article, we have included proper examples with detailed explanations for a better understanding for you. We also learned about how we should think for a solution and then make optimizations in our code in such kinds of problems.

We also discussed two well-explained approaches along with some suitable examples to solve this problem. We also covered in detail how both of the approaches work and what is the significance of. We discussed their time complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers can refer to this article. 

That’s why this article also contains well-explained codes for all the approaches in the most popular languages along with their respective outputs attached to the article for a better understanding of a wide range of our readers. 

We sincerely hope that this article has walked you through some deep and important concepts and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article.

Happy Learning!

People are also reading:

Leave a Reply

Your email address will not be published. Required fields are marked *