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).
Solution
At the first glance, I have no clue about this considering its time complexity constraint. But after checking its examples by the index (0base 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 = (size1i)*2, otherwise;
The implementation then can be simple as follows ensuring time complexity O(n) and space complexity O(1):


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