Rearrange an array in maximum minimum form

Posted in /  

Rearrange an array in maximum minimum form

Vinay Khatri
Last updated on September 14, 2022

    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

    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"; ?>
    
     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:

    Tags:
    array

    Leave a Comment on this Post

    0 Comments