Rearrange Array in Max/Min Form — Medium Problem & Solution

Problem statement

You are given an array arr sorted in ascending order. Rearrange it so that it alternates largest, smallest, second largest, second smallest, and so on.

Return the rearranged array.

Example 1

Input: arr = [1,2,3,4,5,6]
Output: [6,1,5,2,4,3]
Explanation: Largest 6, smallest 1, then 5 and 2, then 4 and 3.

Example 2

Input: arr = [10,20,30,40,50,60,70]
Output: [70,10,60,20,50,30,40]
Explanation: An odd length leaves the middle element last.

Example 3

Input: arr = [4]
Output: [4]

Constraints

• 1 <= arr.length <= 100000
• 1 <= arr[i] <= 1000000
• arr is given in ascending order.

How to solve Rearrange Array in Max/Min Form

Sorted input means the n-th largest is at the right pointer and the n-th smallest at the left pointer, so the required order is just an alternating read from the two ends.

Approach

1. Set lo = 0 and hi = n - 1.
2. While lo <= hi: append arr[hi] and decrement hi; then, if the pointers have not crossed, append arr[lo] and increment lo.
3. Return the collected values.

Why it works

Each step consumes exactly the current maximum then the current minimum of the untouched middle, which is the pattern the statement asks for. The inner guard is what handles an odd length, where the final write has no partner.

Complexity

• Time — O(n)
• Space — O(n) for the output — the classic version does it in place with a modular-arithmetic trick

Pitfalls

• Writing the smallest first — the sequence starts with the largest.
• An odd length appends one extra element from the left pointer; forgetting the guard reads past hi.

Reference solution

Python

from typing import List

def rearrangeMaxMin(arr: List[int]) -> List[int]:
    out = []
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        out.append(arr[hi])
        hi -= 1
        if lo <= hi:
            out.append(arr[lo])
            lo += 1
    return out

JavaScript

var rearrangeMaxMin = function(arr) {
    var out = [];
    var lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        out.push(arr[hi]);
        hi--;
        if (lo <= hi) { out.push(arr[lo]); lo++; }
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium