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 <= 1000001 <= arr[i] <= 1000000arr is given in ascending order.
Hints for Rearrange Array in Max/Min Form
Hint 1
The array is already sorted, so the largest and smallest remaining values are always at the two ends.
Hint 2
Two pointers, one at each end, taking turns — the right one goes first.
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
- Set
lo = 0andhi = n - 1. - While
lo <= hi: appendarr[hi]and decrementhi; then, if the pointers have not crossed, appendarr[lo]and incrementlo. - 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 outJava
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