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}
Input: arr[] = {1, 2, 3, 4, 5, 6}
Output: arr[] = {6, 1, 5, 2, 4, 3}
We have discussed a solution in below post:
Rearrange an array in maximum minimum form | Set 1 : The solution discussed here requires extra space, how to solve this problem with O(1) extra space.
In this post a solution that requires O(n) time and O(1) extra space is discussed. The idea is to use multiplication and modular trick to store two elements at an index.
even index : remaining maximum element.
odd index : remaining minimum element.
max_index : Index of remaining maximum element
(Moves from right to left)
min_index : Index of remaining minimum element
(Moves from left to right)
Initialize: max_index = 'n-1'
min_index = 0
max_element = arr[max_index] + 1 //can be any element which is more than the maximum value in array
For i = 0 to n-1
If 'i' is even
arr[i] += arr[max_index] % max_element * max_element
max_index--
ELSE // if 'i' is odd
arr[i] += arr[min_index] % max_element * max_element
min_index++
How does expression “arr[i] += arr[max_index] % max_element * max_element” work ?
The purpose of this expression is to store two elements at index arr[i]. arr[max_index] is stored as multiplier and “arr[i]” is stored as remainder. For example in {1 2 3 4 5 6 7 8 9}, max_element is 10 and we store 91 at index 0. With 91, we can get original element as 91%10 and new element as 91/10.
Below implementation of the above idea:
C++
// C++ program to rearrange an array in minimum// maximum form#include <bits/stdc++.h>using namespace std;// Prints max at first position, min at second position// second max at third position, second min at fourth// position and so on.void rearrange(int 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 int max_elem = 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] % max_elem) * max_elem; max_idx--; } // at odd index : we have to put minimum element else { arr[i] += (arr[min_idx] % max_elem) * max_elem; min_idx++; } } // array elements back to it's original form for (int i = 0; i < n; i++) arr[i] = arr[i] / max_elem;}// Driver program to test above functionint main(){ int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; int n = sizeof(arr) / sizeof(arr[0]); cout << "Original Arrayn"; 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
// Java program to rearrange an// array in minimum maximum formpublic class Main { // Prints max at first position, min at second // position second max at third position, second // min at fourth position and so on. public static void rearrange(int 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 int max_elem = 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] % max_elem) * max_elem; max_idx--; } // at odd index : we have to put minimum element else { arr[i] += (arr[min_idx] % max_elem) * max_elem; min_idx++; } } // array elements back to it's original form 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, 7, 8, 9 }; int n = arr.length; System.out.println("Original Array"); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); rearrange(arr, n); System.out.print("\nModified Array\n"); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); }}// This code is contributed by Swetank Modi |
Python3
# Python3 program to rearrange an # array in minimum maximum form# Prints max at first position, min at second position# second max at third position, second min at fourth# position and so on.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 max_elem = arr[n-1] + 1 # Traverse array elements for i in range(0, n) : # At even index : we have to put maximum element if i % 2 == 0 : arr[i] += (arr[max_idx] % max_elem ) * max_elem max_idx -= 1 # At odd index : we have to put minimum element else : arr[i] += (arr[min_idx] % max_elem ) * max_elem min_idx += 1 # array elements back to it's original form for i in range(0, n) : arr[i] = arr[i] / max_elem # Driver Codearr = [1, 2, 3, 4, 5, 6, 7, 8, 9]n = len(arr)print ("Original Array")for i in range(0, n): print (arr[i], end = " ") rearrange(arr, n)print ("\nModified Array")for i in range(0, n): print (int(arr[i]), end = " ") # This code is contributed by Shreyanshi Arun. |
C#
// C# program to rearrange an// array in minimum maximum formusing System;class main { // Prints max at first position, min at second // position, second max at third position, second // min at fourth position and so on. public static void rearrange(int[] 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 int max_elem = 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] % max_elem) * max_elem; max_idx--; } // at odd index : we have to // put minimum element else { arr[i] += (arr[min_idx] % max_elem) * max_elem; min_idx++; } } // array elements back to it's original form 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, 7, 8, 9 }; 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] + " "); }}// This code is contributed by vt_m. |
Javascript
<script>// JavaScript program to rearrange an array in minimum // maximum form // Prints max at first position, min at second position // second max at third position, second min at fourth // position and so on. 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 max_elem = 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] % max_elem) * max_elem; max_idx--; } // at odd index : we have to put minimum element else { arr[i] += (arr[min_idx] % max_elem) * max_elem; min_idx++; } } // array elements back to it's original form for (let i = 0; i < n; i++) arr[i] = Math.floor(arr[i] / max_elem); } // Driver program to test above function let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]; let n = arr.length; document.write("Original Array<br>"); for (let i = 0; i < n; i++) document.write(arr[i] + " "); rearrange(arr, n); document.write("<br>Modified Array<br>"); for (let i = 0; i < n; i++) document.write(arr[i] + " "); // This code is contributed by Surbhi Tyagi.</script> |
PHP
<?php// PHP program to rearrange an // array in minimum-maximum form// Prints max at first position, // min at second position// second max at third position, // second min at fourth// position and so on.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 $max_elem = $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] % $max_elem) * $max_elem; $max_idx--; } // at odd index : we have to // put minimum element else { $arr[$i] += ($arr[$min_idx] % $max_elem) * $max_elem; $min_idx++; } } // array elements back to // it's original form for ($i = 0; $i < $n; $i++) $arr[$i] = (int)($arr[$i] / $max_elem);}// Driver Code$arr = array(1, 2, 3, 4, 5, 6, 7, 8, 9);$n = sizeof($arr);echo "Original Array" . "\n";for ($i = 0; $i < $n; $i++) echo $arr[$i] . " ";rearrange($arr, $n);echo "\nModified Array\n";for ($i = 0; $i < $n; $i++) echo $arr[$i] . " ";// This code is contributed// by Akanksha Rai(Abby_akku) |
Output
Original Arrayn1 2 3 4 5 6 7 8 9 Modified Array 9 1 8 2 7 3 6 4 5
Time Complexity: O(n)
Auxiliary Space: O(1), as no extra space is used
Thanks Saurabh Srivastava and Gaurav Ahirwar for suggesting this approach.
Another Approach:
C++
#include <iostream>using namespace std;int main(){ int a[] = { 11, 12, 13, 14, 15, 16 }; int n = sizeof(a) / sizeof(a[0]); int last[n]; int min = 0, max = n - 1; int count = 0; for (int i = 0; min <= max; i++) { if (count % 2 == 0) { last[i] = a[max]; max--; } else { last[i] = a[min]; min++; } count++; } for (int i = 0; i < n; i++) cout << last[i] << " "; return 0;} |
Java
import java.util.Arrays;// Defining the classpublic class Main { // Main function public static void main(String[] args) { // Initializing an array a int[] a = { 11, 12, 13, 14, 15, 16 }; // Finding the length of array a int n = a.length; // Initializing an array last with size n int[] last = new int[n]; // Initializing variables min and max int min_val = 0; int max_val = n - 1; // Initializing a variable count to keep track of // iterations int count = 0; for (int i = 0; i < n; i++) { // If count is even, store the value of // a[max_val] in last[i] and decrement max_val if (count % 2 == 0) { last[i] = a[max_val]; max_val -= 1; } // If count is odd, store the value of // a[min_val] in last[i] and increment min_val else { last[i] = a[min_val]; min_val += 1; } // Increment the value of count count += 1; } // Printing the values in array last System.out.println(Arrays.toString(last)); }} |
Python3
# Initializing an array aa = [11, 12, 13, 14, 15, 16]# Finding the length of array an = len(a)# Initializing an array last with size nlast = [0] * n# Initializing variables min and maxmin_val = 0max_val = n - 1# Initializing a variable count to keep track of iterationscount = 0# Looping through the arrayfor i in range(n): # If count is even, store the value of #a[max_val] in last[i] and decrement max_val if count % 2 == 0: last[i] = a[max_val] max_val -= 1 # If count is odd, store the value of # a[min_val] in last[i] and increment min_val else: last[i] = a[min_val] min_val += 1 # Increment the value of count count += 1# Printing the values in array lastfor i in range(n): print(last[i], end=' ') |
C#
// C# program to rearrange // an array in minimum // maximum formusing System;class GFG{ static public void Main () { int[] a = { 11, 12, 13, 14, 15, 16 }; int n = a.Length; int[] last = new int[n]; int min = 0, max = n - 1; int count = 0; for (int i = 0; min <= max; i++) { if (count % 2 == 0) { last[i] = a[max]; max--; } else { last[i] = a[min]; min++; } count++; } for (int i = 0; i < n; i++) Console.Write(last[i] + " "); }} |
Javascript
// Initializing an array alet a = [11, 12, 13, 14, 15, 16];// Finding the length of array alet n = a.length;// Initializing an array last with size nlet last = new Array(n).fill(0);// Initializing variables min and maxlet min_val = 0;let max_val = n - 1;// Initializing a variable count to keep track of iterationslet count = 0;// Looping through the arrayfor (let i = 0; i < n; i++) {// If count is even, store the value of//a[max_val] in last[i] and decrement max_valif (count % 2 == 0) {last[i] = a[max_val];max_val--;}// If count is odd, store the value of// a[min_val] in last[i] and increment min_valelse {last[i] = a[min_val];min_val++;}// Increment the value of countcount++;}// Printing the values in array lastconsole.log(last.join(' '));// This code is contributed by adityash4x71 |
Output
16 11 15 12 14 13
Time Complexity: O(n), where n is the size of the array
Auxiliary Space: O(n)
Thanks Apollo Doley for suggesting this approach.
This article is contributed by Aarti_Rathi Nishant Singh . If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
