Rearrange Array in Max/Min Form

Medium
613.

Rearrange Array in Max/Min Form

Rearrange Array in Max/Min Form is a medium coding problem on arrays and two pointers, asked in Amazon, Accenture and Paytm interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var rearrangeMaxMin = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Rearrange Array in Max/Min Form — Problem & Solution

Rearrange Array in Max/Min Form solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Rearrange Array in Max/Min Form is a medium coding problem on arrays and two pointers, asked in Amazon, Accenture and Paytm interviews.

  • Difficulty: Medium
  • Topics: Arrays, Two Pointers
  • Asked at: Amazon, Accenture, Paytm
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Rearrange Array in Max/Min Form

  1. Hint 1

    The array is already sorted, so the largest and smallest remaining values are always at the two ends.

  2. Hint 2

    Two pointers, one at each end, taking turns — the right one goes first.

  3. Hint 3

    Stop when the pointers cross; with an odd length the last element written comes from the left pointer.

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

Java

public static int[] rearrangeMaxMin(int[] arr) {
    int n = arr.length;
    int[] out = new int[n];
    int lo = 0, hi = n - 1, k = 0;
    while (lo <= hi) {
        out[k++] = arr[hi--];
        if (lo <= hi) out[k++] = arr[lo++];
    }
    return out;
}

C++

vector<int> rearrangeMaxMin(vector<int>& arr) {
    vector<int> out;
    int lo = 0, hi = (int) arr.size() - 1;
    while (lo <= hi) {
        out.push_back(arr[hi--]);
        if (lo <= hi) out.push_back(arr[lo++]);
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Two Pointers Technique