Rearrange Array Alternately (Max–Min)

Problem Statement

Given a sorted array, rearrange its elements in-place in such a way that:

• The first element is the maximum
• The second element is the minimum
• The third element is the second maximum
• The fourth element is the second minimum
• And so on…

Constraint: Must be done in O(n) time and O(1) extra space if possible.

Example 1

Input

arr = [1, 2, 3, 4, 5, 6]

Output

[6, 1, 5, 2, 4, 3]

Explanation

Max → 6, Min → 1, 2nd Max → 5, 2nd Min → 2, ...

Example 2

Input

arr = [10, 20, 30, 40, 50]

Output

[50, 10, 40, 20, 30]

Why This Problem Is Important

• Tests understanding of array indexing
• Evaluates in-place modification skills
• Introduces the concept of encoding multiple numbers in a single array slot
• Common in interview and competitive programming

Approaches to Solve the Problem

1. Using Extra Array (Simplest)
2. In-Place Encoding Method (Optimized, O(1) space)

Approach 1: Using Extra Array

Idea

• Use two pointers:
  • start = 0 → minimum element
  • end = n-1 → maximum element
• Place elements alternatively in a new array
• Copy back to original array

Algorithm

1. Initialize start = 0, end = n-1
2. Create result[n]
3. Loop i = 0 to n-1:
   • If i is even → result[i] = arr[end--]
   • Else → result[i] = arr[start++]
4. Copy result back to arr

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(n)

C++ Implementation

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = 6;
    int result[n];
    int start = 0, end = n - 1;

    for(int i = 0; i < n; i++) {
        if(i % 2 == 0)
            result[i] = arr[end--];
        else
            result[i] = arr[start++];
    }

    for(int i = 0; i < n; i++)
        arr[i] = result[i];

    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

Output

6 1 5 2 4 3

JavaScript

let arr = [1, 2, 3, 4, 5, 6];
let n = arr.length;

let result = [];
let start = 0;
let end = n - 1;

for (let i = 0; i < n; i++) {
    if (i % 2 === 0) {
        result[i] = arr[end--]; // Pick max
    } else {
        result[i] = arr[start++]; // Pick min
    }
}

// Copy back to original array
for (let i = 0; i < n; i++) {
    arr[i] = result[i];
}

console.log(arr);

Output

[6, 1, 5, 2, 4, 3]

Approach 2: In-Place Encoding (O(1) Space)

Idea

• Store two numbers in one element using modulus encoding
• Formula:

arr[i] = arr[i] + (arr[max_idx] % max_element) * max_element   // For max positions
arr[i] = arr[i] + (arr[min_idx] % max_element) * max_element   // For min positions

• After encoding, divide each element by max_element to decode

Step 1: Find max_element = arr[n-1] + 1
Step 2: Use two pointers min_idx and max_idx
Step 3: Encode values
Step 4: Decode by dividing each element by max_element

Algorithm

1. max_idx = n-1, min_idx = 0
2. max_elem = arr[n-1] + 1
3. For i = 0 to n-1:
   • If i % 2 == 0 → arr[i] += (arr[max_idx] % max_elem) * max_elem; max_idx--
   • Else → arr[i] += (arr[min_idx] % max_elem) * max_elem; min_idx++
4. Divide each element by max_elem

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

C++ Implementation (In-Place)

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = 6;

    int max_idx = n - 1, min_idx = 0;
    int max_elem = arr[n-1] + 1;

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

    for(int i = 0; i < n; i++)
        arr[i] = arr[i] / max_elem;

    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";

    return 0;
}

Output

6 1 5 2 4 3

Python Implementation (In-Place)

arr = [1, 2, 3, 4, 5, 6]
n = len(arr)
max_idx = n - 1
min_idx = 0
max_elem = arr[-1] + 1

for i in range(n):
    if i % 2 == 0:
        arr[i] += (arr[max_idx] % max_elem) * max_elem
        max_idx -= 1
    else:
        arr[i] += (arr[min_idx] % max_elem) * max_elem
        min_idx += 1

for i in range(n):
    arr[i] = arr[i] // max_elem

print(arr)

Output

[6, 1, 5, 2, 4, 3]

Javascript

let arr2 = [1, 2, 3, 4, 5, 6];
let n2 = arr2.length;

let max_idx = n2 - 1;
let min_idx = 0;
let max_elem = arr2[n2 - 1] + 1; // Any number greater than max element

for (let i = 0; i < n2; i++) {
    if (i % 2 === 0) {
        // Place max element at even index
        arr2[i] += (arr2[max_idx] % max_elem) * max_elem;
        max_idx--;
    } else {
        // Place min element at odd index
        arr2[i] += (arr2[min_idx] % max_elem) * max_elem;
        min_idx++;
    }
}

// Decode elements
for (let i = 0; i < n2; i++) {
    arr2[i] = Math.floor(arr2[i] / max_elem);
}

console.log(arr2);

Output

[6, 1, 5, 2, 4, 3]

Dry Run (Encoding Method)

• Divide each by 7 → [6,1,5,2,4,3]

Summary

• Two approaches:
  1. Extra Array → Simple, O(n) space
  2. In-place Encoding → Optimal, O(1) space
• Useful in interviews for in-place rearrangement problems
• Works only on sorted arrays

Next Problems in the series.

Leaders in an Array