Given an array A. Rearrange the array in such a way that A <= A but A >= A and A <= A upto A[N-1] <>= A[N] (depending on the parity of N) is satisfied.
A[i] <= A[i + 1] if i is odd.
A[i] >= A[i + 1] if i is even.
- O(N logN) Solution: Sort the array A. Pick A, then pick A[N - 1], A, A[N - 2] etc upto Nth element.
- O(N) Solution: Go from A to A[N] in left to right order, if at any point of time, condition of given inequalities are not satisfied, then swap the elements in such a way that the condition is satisfied. We will prove in next section why this approach will always work.
O(N logN) Solution:
First step is to sort the array A.
Now we have to build an array B such that it contains the elements of A in rearranged way. They B array is our answer to the given problem.
We will first add A in B, then A[N - 1], then A, A[N - 2], A, A[N - 3] etc.
Note that this approach is always going to produce correct result because at the current step we are always picking the smallest and largest possible numbers which we can still pick, hence the inequality conditions given in the problem are never violated.
Let A = [4, 3, 5, 1].
Sort the array A.
A now becomes = [1, 3, 4, 5].
Our array B will be [1, 5, 3, 4].
Complexity: O(N log N).
All we need to do is to sorting of an array, All other operation costs only O(N) time. Hence time complexity is O(N log N).
We will go from left to right from A to A[N]. If at any position, our inequality condition is unsatisfied, we will make a swap of i and i + 1 entries.
Let A = [4, 3, 5, 1, 2].
If we are first element (i = 1): A <= A is not satisfied, so we will swap A and A.
So A will now become: [3, 4, 5, 1, 2]
Now we are at second element (i = 2): A >= A is not satisfied, so we will swap A and A.
So A will now become: [3, 5, 4, 1, 2]
Now we are at third element (i = 3): A <= A is not satisfied, so we will swap A and A.
So A will now become: [3, 5, 1, 4, 2]
Now we are at fourth element (i = 4): A >= A is satisfied, so we dont need to swap.
So A will remain as it is: [3, 5, 1, 4, 2]
Proof Of Correctness:
Assume that a, b, c, be the leftmost(Ordered from A to A[N], A is leftmost, A[N] is rightmost) elements of the array A for which condition is not satisfied. Let us assume that a be the elements which just precedes b. (ie order of occurrence of elements is a, b, c)
Let us suppose we want b >= c. (a <= b).
According to our assumption, a <= b is already satisfied, but b >= c is not satisfied (ie b < c)
Now on swapping b and c, our new order of elements will be a, c, b.
Note that now in this order a <= c(because a <= b < c).
and we have c >= b. (because c > b).
We can handle the second case in the exactly similar way too (Case when a >= b is satisfied but b <= c is not satisfied). This case is left for readers to prove.
For each index i from 1 to N, we can make at most 1 swap, Swap operation is constant operation, Hence we will only make total O(N) operations.