.png)
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
- Using Extra Array (Simplest)
- 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
- Initialize start = 0, end = n-1
- Create result[n]
- Loop i = 0 to n-1:
- If i is even → result[i] = arr[end--]
- Else → result[i] = arr[start++]
- 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
- max_idx = n-1, min_idx = 0
- max_elem = arr[n-1] + 1
- 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++
- 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)
| i | Original | Encoded (temp) | Max/Min Pick |
|---|---|---|---|
| 0 | 1 | 1 + 6*7 = 43 | max → 6 |
| 1 | 2 | 2 + 1*7 = 9 | min → 1 |
| 2 | 3 | 3 + 5*7 = 38 | max → 5 |
| 3 | 4 | 4 + 2*7 = 18 | min → 2 |
| 4 | 5 | 5 + 4*7 = 33 | max → 4 |
| 5 | 6 | 6 + 3*7 = 27 | min → 3 |
- Divide each by 7 → [6,1,5,2,4,3]
Summary
- Two approaches:
- Extra Array → Simple, O(n) space
- In-place Encoding → Optimal, O(1) space
- Useful in interviews for in-place rearrangement problems
- Works only on sorted arrays
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
