# Rearrange Array Alternately

## Problem Statement

Given a sorted array A[] consisting of N integers. The task is to rearrange the array alternatively i.e. the first element should be maxed value, second should be min value, third should be the second max, fourth should be the second min, and so on.

Examples:
Input: A[] = {1, 2, 3, 4, 5, 6, 7}
Output: {7, 1, 6, 2, 5, 3, 4}
Explanation:

Input: A[] = {1, 2, 3, 4, 5, 6}
Output: {6, 1, 5, 2, 4, 3}

## Auxiliary Space Approach

The idea is to use a two-pointer approach. The below diagram shows the approach

Algorithm

• Consider two pointers low = 0 and high = N – 1, which are pointing to the first and last element of the array.
• Create a temp[] array for storing the resultant array.
• Start copying the last element of the array followed by the first element and so on into the temp array.
• Repeat the above process, until the low pointer becomes less than or equal to the high pointer.

### C++ Code For Auxiliary Space Approach

```
void rearrange(int A[], int N)
{
int temp[N];
int low = 0, high = N - 1;
int flag = true;

for (int i = 0; i < N; i++) {
if (flag)
temp[i] = A[high--];
else
temp[i] = arr[low++];

flag = !flag;
}
for (int i = 0; i < N; i++)
A[i] = temp[i];
}```

### Java Code For Auxiliary Space Approach

```static void rearrange(int[] A, int N)
{
int temp[] = A.clone();
int low = 0, high = N - 1;
boolean flag = true;

// Store result in temp[]
for (int i = 0; i < N; i++) {
if (flag)
A[i] = temp[high--];
else
A[i] = temp[low++];

flag = !flag;
}
}```

### Python Code For Auxiliary Space Approach

```def rearrange(A, N):
temp = N*[None]
low, high = 0, N - 1

flag = True

for i in range(N):
if flag is True:
temp[i] = A[high]
high -= 1
else:
temp[i] = arr[low]
low += 1

flag = bool(1-flag)

for i in range(N):
A[i] = temp[i]
return A```

Time Complexity: O(N) where N is the size of the array A[].
Space Complexity: O(N), as extra space, is used.

## Constant Space Approach – Efficient Approach

The efficient approach solves the problem in place without considering any auxiliary array.

The idea is to use multiplication and modular tricks to store two elements at the same index. Observe the below example

We will use the same approach to solve the problem.

Algorithm

• Initialize two pointers max_idx = 0 and min_idx = N – 1, where N is the size of the array.
• Initialise an element mx  equal to 1 + maximum element of the array. Note : You can initialise mx to any integer greater than the maximum element.
• Iterate over the array and perform the following operations:
• If the current index is even:
• Update A[i] = A[i] + (A[max_idx] % mx) * mx
• Decrement max_idx by 1.
• If the current index is odd:
• Update A[i] = A[i] + (A[min_idx] % mx) * mx
• Increment min_idx by 1.
• To update the array element back to its original form, divide A[i] by mx.

### C++ Code For Constant Space Approach

```void rearrange(int A[], int N)
{

int max_idx = N - 1, min_idx = 0;

int mx = A[N - 1] + 1;

for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
A[i] += (A[max_idx] % mx) * mx;
mx--;
}
else {
A[i] += (A[min_idx] % mx) * mx;
min_idx++;
}
}

for (int i = 0; i < n; i++)
A[i] = A[i] / max_elem;
}```

### Java Code For Constant Space Approach

```public static void rearrange(int A[], int N){
int max_idx = N - 1, min_idx = 0;
int mx = A[N - 1] + 1;
for (int i = 0; i < N; i++) {
if (i % 2 == 0) {
A[i] += (A[max_idx] % mx) * mx;
max_idx--;
}
else {
A[i] += (A[min_idx] % mx) * mx;
min_idx++;
}
}
for (int i = 0; i < n; i++)
A[i] = A[i] / mx;
}```

### Python Code For Constant Space Approach

```def rearrange(A, N):
max_idx = N - 1
min_idx = 0

mx = A[n-1] + 1

for i in range(0, N) :
if i % 2 == 0 :
A[i] += (A[max_idx] % mx ) * mx
max_idx -= 1

else :
A[i] += (A[min_idx] % mx ) * mx
min_idx += 1

for i in range(0, N) :
A[i] = A[i] / mx```

Time Complexity: O(N) where N is the size of the array A[].
Space Complexity: O(1), as no extra space is used.

## Practice Question

Rearrange Array

What is the time and complexity of arranging in max-min form?
The time complexity is O(N). The space complexity is O(N) for the naive approach and O(1) using the efficient approach.

Do you need to sort the array A[]?
If the given array is unsorted, then we need to sort the array first and then apply the given approach.

##### Previous Post ## Fractional Knapsack Problem

##### Next Post ## Number of Pairs

Crack your next tech interview with confidence!
Take a free mock interview, get instant⚡️ feedback and recommendation💡