Convert array

Given an array [a1, a2, …, aN, b1, b2, …, bN, c1, c2, …, cN]  convert it to [a1, b1, c1, a2, b2, c2, …, aN, bN, cN] in-place using constant extra space.

Brute force Solution

The first solution every kid in town will think of is to create a duplicate array and copy the elements at their appropriate position in the second array.

[ 0 1 2 3 4 5 6 7 8 ]

[ 0 3 6 1 4 7 2 5 8 ]

We've to divide the array into 3 parts:

[ 0 1 2 ] [ 3 4 5 ] [ 6 7 8 ]

Now how do we map ith index to the converted array index. You'll notice that if we treat each them as a 3 sized blocked then the index of the block can be found by moduli operator:

index of the block = (i%3)

| Block 0 | Block 1 | Block 2 |

[ 0 1 2 3 4 5 6 7 8 ] ( i )
[ 0 1 2 0 1 2 0 1 2 ] (i%3) Block index
[ 0 3 6 0 3 6 0 3 6 ] X 3

Once we've the block index we need to find the index within the block where we need to put the element. Here's where the division operator will help us:

[ 0 1 2 3 4 5 6 7 8 ] ( i )
[ 0 0 0 1 1 1 2 2 2 ] ( i/3 )

The first three elements sits as the 1st index in each block.
The second three elements sits as the 2nd index in each block.
The third three elements sits as the 3rd index in each block.

The formula we get is: (N * (i%N)) + i/N

Here is how it works:

[ 0 1 2 3 4 5 6 7 8 ]
[ 0 1 2 0 1 2 0 1 2 ] X 3
[ 0 0 0 1 1 1 2 2 2 ]

[ 0 3 6 1 4 7 2 5 8 ]

We've the formula, we've extra space. All we need to do now is to loop the array and set the element in the resultant array using the index we get from the above formula.

Time Complexity: O(N)
Space Complexity: O(N)

Great. Is it ?
What if I told you that we can do this without the extra space ?

A Better Solution

Not using extra space means making use of the array itself and modifying the array in place. So we need to swap the numbers to their appropriate position.

What if we just swap the element with the index we get from the previous formula ?

Let's say swapIndex = (N * (i%N)) + i/N. So we can have three cases here:

if i == swapIndex

Do nothing as it's already at the correct place.

if i < swapIndex

This means we've not reached the swap index. We can swap the elements for now. Things will get interesting in the third case.

if i > swapIndex

This means that we're past the swap index. The element at the swapIndex has already been swapped with the appropriate position. 

We calculate the swapping index for the swapIndex. If we find an index which is greater than i then we simply swap it. Otherwise we find the swapping index again with the previous formula.

The gist here is that a swapIndex before i is already at the correct position.

Here's a dry run:

[ 0 1 2 3 4 5 6 7 8 ], swapIndex = 0, i = 0, i == swapIndex
[ 0 3 2 1 4 5 6 7 8 ], swapIndex = 3, i = 1, i < swapIndex
[ 0 3 6 1 4 5 2 7 8 ], swapIndex = 6, i = 2, i < swapIndex
[ 0 3 6 1 4 5 2 7 8 ], swapIndex = 1, i = 3, i > swapIndex
[ 0 3 6 1 4 5 2 7 8 ], swapIndex = 3, i = 3, update swapIndex
[ 0 3 6 1 4 5 2 7 8 ], swapIndex = 4, i = 4, i == swapIndex
[ 0 3 6 1 4 7 2 5 8 ], swapIndex = 7, i = 5, i < swapIndex
[ 0 3 6 1 4 7 2 5 8 ], swapIndex = 2, i = 6, i > swapIndex
[ 0 3 6 1 4 7 2 5 8 ], swapIndex = 6, i = 6, update swapIndex
[ 0 3 6 1 4 7 2 5 8 ], swapIndex = 5, i = 7, i > swapIndex
[ 0 3 6 1 4 7 2 5 8 ], swapIndex = 7, i = 7, update swapIndex
[ 0 3 6 1 4 7 2 5 8 ], swapIndex = 8, i = 8, i > swapIndex

Time Complexity: O(N)
Space Complexity: O(1)