- Problem Statement
- Auxiliary Space Approach
- C++ Code For Auxiliary Space Approach
- Java Code For Auxiliary Space Approach
- Python Code For Auxiliary Space Approach
- Constant Space Approach – Efficient Approach
- C++ Code For Constant Space Approach
- Java Code For Constant Space Approach
- Python Code For Constant Space Approach
- Practice Question
- Frequently Asked Questions

## 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] = A[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] = A[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 =**and**N – 1****min_idx =0**, 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.

- Update
- If the current index is
**odd**:- Update
**A[i] = A[i] + (A[min_idx] % mx) * mx** - Increment
**min_idx**by 1.

- Update

- If the current index is
- 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 max_elem = A[N - 1] + 1; for (int i = 0; i < N; i++) { if (i % 2 == 0) { A[i] += (A[max_idx] % max_elem) * max_elem; max_idx--; } else { A[i] += (A[min_idx] % max_elem) * max_elem; 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

## Frequently Asked Questions

**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.