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.
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, the 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 to solve 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.
Here, 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 and one index further.
Moreover, we will be following the same pattern unless the start pointer becomes less than or equal to the end pointer.
Algorithm
- Create an array to store a rearranged array.
- 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.
- Create a flag element that will be initially true to indicate if there are remaining elements to be copied.
- Store the rearranged values in the temp array.
- Copy the elements of the temp array.
- 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
- 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.
- Initialize the array's maximum element.
- Iterate over the array and store max elements in a decreasing order at even indices.
- Store the min elements in increasing order at odd indices.
- Storing elements of the array in their original way.
- 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"; ?>
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>");
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.
Also, we have included proper examples with detailed explanations for a better understanding for you. We also learned about how we should think of a solution and then make optimizations in our code for such kinds of problems. We also discussed two well-explained approaches along with some suitable examples to solve this problem.
Moreover, we also covered in detail how both of the approaches work and what is their 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 Comment on this Post