Given an array in A = [a1,a2,a3,….an, b1, b2,b3,…bn,c1,c2,c3,…..cn] form
Rearrange above array in below manner: A = [a1,b1,a2,b3,a3,b3,……an,bn]
If input A =[1,2,3,4,5,6,7,8,9,10],
Output should A =[1,6,2,7,3,8,4,9,5,10]
Above problem can be solved easily using extra space. However, let’s optimize the space requirement. Algorithm is based on rotation of array.
We will process each group from right to left. Put last element of group at the start of the array and rotate the array till that point., repeat till all elements are not processed.
- Take each group one by one.
- Take the last element of the current group and save it.
- Rotate the given array from 0 to index of last element of current group.
- Put last element saved in step 2 at start of the array.
- Repeat above steps till all elements are processed.
Let’s take an example
A = [1,2,3,,x,y,z, 4,5,6]
There are three groups [1,2,3], [x,y,z] and [4,5,6]
Now we will take last element of group [4,5,6] i.e 6
And we will right rotate the entire array till position of 6. So A becomes
A = [6,1,2,3,x,y,z,4,5]
Now we take last element of group [x,y,z] i.e. z
Now right rotate array till position of z. So array becomes
A = [z,6,1,2,3,x,y,4,5]
Similarly for group [1,2,3] i.e 3
Now last element of group [4,5,6] is 5 as we have considered 6 earlier. After doing processing which we did for 6, array will be
A = [5,3,z,6,1,2,x,y,4]
After processing y.
A = [y,5,3,z,6,1,2,x,4]
After processing 2
A = [2,y,5,3,z,6,1,x,4]
In similar fashion we will process remaining 4,x, and 1.
Output will be A = [1,x,4,2,y,5,3,z,6]
Complexity of code will be O(N^2) and space complexity is O(1)