Search⌘ K
AI Features
Home
Courses
Data Structures for Coding Interviews in C#

Solution Review: Rearrange Sorted Array in Max/Min Form

Explore how to rearrange a sorted array in max/min form using two C# solutions. Understand an approach with extra space and a space-optimized method that stores two elements at one index. Learn to implement these with O(n) time complexity for efficient coding.

We'll cover the following...

Solution 1: Creating a new array

C#
namespace chapter_2
{
    class Challenge10
    {
        // Rearrange Sorted Array in Max/Min Form
        static void maxMin(int []arr, int size)
        {
            //Create a result array to hold re-arranged version of given arr
            int[] result = new int[size];
            int pointerSmall = 0,     //PointerSmall => Start of arr
            pointerLarge = size - 1;   //PointerLarge => End of arr
            //Flag which will help in switching between two pointers
            bool switchPointer = true;
            for (int i = 0; i < size; i++)
            {
                if (switchPointer)
                    result[i] = arr[pointerLarge--]; // copy large values
                else
                    result[i] = arr[pointerSmall++]; // copy small values
                switchPointer = !switchPointer;   // switching between samll and large
            }
            for (int j = 0; j < size; j++)
            {
                arr[j] = result[j];    // copying to original array
            }
           // delete[] result;
        }
        static void Main(string[] args)
        {
            int size = 6;
            int []arr = { 1, 2, 3, 4, 5, 6 };
            Console.Write("Array before min/max: ");
            for (int i = 0; i < size; i++)
                Console.Write(arr[i] + " ");
            Console.WriteLine("");
            maxMin(arr, size);
            Console.Write("Array after min/max: ");
            for (int i = 0; i < size; i++)
                Console.Write(arr[i] + " ");
        }
    }
}

Explanation

In this solution, first create an empty array result whose size is equal to the size of the original array arr. Then start iterating over the array. Store the maximum number in the start of the array, then store the minimum number next to it, and so on. In the end, you should store the result array to the original array. Look at the example below:

Time complexity

The time complexity of this problem is ...