ReArrange Array Alternately

Problem Link : Link
Companies : Zoho

Hey everyone! Here's an intriguing problem that could be a great addition to your interview preparation. Let’s dive in and break it down together!

Problem :

Given an array of positive integers. Your task is to rearrange the array elements alternatively i.e. first element should be the max value, the second should be the min value, the third should be the second max, the fourth should be the second min, and so on.
Note: Modify the original array itself. Do it without using any extra space. You do not have to return anything.

Sample Test Case

Input : arr[] = [1, 2, 3, 4, 5, 6]
Output : [6, 1, 5, 2, 4, 3]
Explanation : Max element = 6, min = 1, second max = 5, second min = 2, and so on... The modified array is: [6, 1, 5, 2, 4, 3]

Solution

Brute Force Approach

Intuition:
In a sorted array, the numbers increase sequentially from left to right. We can use this property to arrange the elements alternately.

Approach:

1. Sort the Array: Start by sorting the array in ascending order.

2. Initialize Pointers and Indices:

   • Use two pointers:

     • left pointing to the smallest element (0).

     • right pointing to the largest element (arr.size() - 1).

   • Use two indices:

     • i for even indexes in the result array.

     • j for odd indexes in the result array.

3. Rearrange Elements:

   • While left <= right:

     • Place the element at the right pointer into the even index (i) of the result array.

     • Place the element at the left pointer into the odd index (j) of the result array.

     • Increment left and decrement right to process the next smallest and largest elements.

     • Increment i and j by 2 to move to the next respective indexes.

4. Copy Back to Original Array:

   • Replace the original array elements with the values from the result array.

Time Complexity : O(NlogN)
Space Complexity : O(N)

What if I told you there's a smarter way to solve this problem in just O(Nlog⁡N)O(N \log N)O(NlogN) time while using only O(1)O(1)O(1) extra space? Intrigued? Let’s dive into the details below!

Optimized Approach

Intuition:
What if we could cleverly store two values in a single cell of the array—the original value (current array element) and the new value (the element it should transform into)? Let’s explore how we can derive a formula to achieve this!

Before we dive in, let’s take a look at some basic that will help us understand the approach better.

Max = max(array) + 1 New Value = Arr[i] / Max
Old Value = Arr[i] % Max

We use the maximum element in the array as a reference because it provides a fixed value to help us retrieve the required result. Adding 1 ensures that this value is greater than every other element, making it easy to extract the new value using the modulo operation.

Now that we've discussed the basics, we will apply the following formula in our approach:

Arr[i] = (Arr[maxIdx] % maxElement) * maxElement + Arr[i]

So, why do we use (Arr[maxIdx] % maxElement)? This step is crucial because it allows us to retrieve the original value of Arr[maxIdx], even if it has already been modified. By taking the modulo with maxElement, we ensure that the new value stored at maxIdx doesn’t interfere with the retrieval of the original value during subsequent calculations.

Now that we've covered the basics and understand the formula, we can dive into our approach. Let’s put everything together and see how this method works to solve the problem efficiently!

Approach

Sort the Array:

• Begin by sorting the array in ascending order to easily access the smallest and largest elements.

• sort(arr.begin(), arr.end());

1. Define the Maximum Element:

   • Define a variable maxElement as one greater than the largest element in the sorted array. This will be used as a reference to store two values (the old and new values) in each array element. By doing so, we can easily retrieve the original value during future operations.

   •               maxElement = arr.back() + 1;
     

2. Initialize Pointers:

   • Set maxIdx to the index of the largest element (arr.size() - 1) and minIdx to the index of the smallest element (0). These will be used to fetch the largest and smallest elements alternately during the array traversal.

   •               int maxIdx = arr.size() - 1 , minIdx = 0;
     

3. Traverse and Modify the Array:

   • Use a loop to iterate through the array. For each index i, alternate between inserting the largest element at even indices and the smallest element at odd indices.

   • The value at each index is updated using the formula:
     arr[i] = (arr[maxIdx] % maxElement) * maxElement + arr[i];

     This ensures that both the original value and the new value are stored in the same cell. The % maxElement operation retrieves the previous value of the element (if it has already been modified).

   • After updating the element, adjust the maxIdx or minIdx to move to the next largest or smallest element, respectively.

     •   for (int i = 0; i < arr.size(); i++) {`
                  if (i % 2 == 0) {
                         arr[i] = (arr[maxIdx] % maxElement) maxElement + arr[i];
                         maxIdx--;
                     } else {
                         arr[i] = (arr[minIdx] % maxElement) maxElement + arr[i];
                         minIdx++;
                     }
         }
       

4. Retrieve the Final Values:

   • After the array is updated, each element contains the combined old and new values. To extract the final modified values, divide each element by maxElement (which was added to the array to store two values).

   •   for (int &val : arr) val = val / maxElement;
     

Time Complexity:

• Sorting the array: O(Nlog⁡N)

• Traversing the array and updating values: O(N)

• Final step of dividing by maxElement: O(N)

• Overall Time Complexity: O(NLogN)

Space Complexity:

• Overall Space Complexity: O(1)