Rearrange Array

Rearrange Always

Given an ascending sorted array of positive integers, rearrange the array alternately i.e first element should be maximum value, second minimum value, third second max, fourth second min and so on.

Examples:

  • Input : arr[] = {1, 2, 3, 4, 5, 6, 7}
    Output : arr[] = {7, 1, 6, 2, 5, 3, 4}
  • Input : arr[] = {1, 2, 3, 4, 5, 6}
    Output : arr[] = {6, 1, 5, 2, 4, 3}

Constraint: Expected time complexity is O(n), and space complexity O(1).

test

Solution

At the first glance, I have no clue about this considering its time complexity constraint. But after checking its examples by the index (0-base index), we could easily find it out that it follows the rules as follows (original index -> final index):

  • the first half: 0 -> 1, 1 -> 3, 2 -> 5 …
  • the other half: 3 -> 6, 4 -> 4, 5 -> 2, 6 -> 2 …
    So the conclusion is this: j = 2*i+1, if i < size/2; j = (size-1-i)*2, otherwise;

The implementation then can be simple as follows ensuring time complexity O(n) and space complexity O(1):

1
2
3
4
5
6
7
8
9
10
11
12
13
void rearrange(vector<int>& arr){
for(int i = 0; i < arr.size(); ++i){
if(arr[i] < 0) continue;
int j = i<arr.size()/2? 2*i+1 : (arr.size()-1-i)*2;
int t = arr[i];
while(arr[j] > 0) {
swap(t, arr[j]);
arr[j] *= -1;
j = j<arr.size()/2? 2*j+1 : (arr.size()-1-j)*2;
}
}
for(auto& n: arr) n = -n;
}

Always welcome new ideas and practical tricks, just leave them in the comments!