Given an array [a1b2c3d4] convert to [abcd1234]

Question

Constraints :

1. O(1) space
2. O(n) Time

It is not a homework question just a interesting question I came across.

Here are some solutions I could think of but nothing that does it in given constraints.

Method 1

*With O(n) memory *

• Divide the array in two parts recursively. ( keep dividing till the size <=2 for each sub problem )
• Sort each sub problem with array first and numbers at end.
• Merge the sub problem arrays

Method 2

In O(n log n) time

• Sort the array based Lexicographical order it becomes 1234abcd
• Reverse both halves of array 4321dcba
• Reverse the whole string abcd1234

Method 3

If range of numbers was defined

Also if the case was that numbers are in a specific range then I can initialize a int say track= 0; And set the appropriate bit when I come across a number in array eg (1 << a[2] ) . 1. Swap alphabets to first half of array 2. Mark numbers in track variable 3. later use track to fill in second half of array.

Method 4 We can use Method 3 with HashMap if we want to remove the constraint of range of integers but then it will need more memory.

Cannot think of a better way to solve the generic problem in O(1) time and O(n) space.

Generic Problem here refers to:

Given a sequence x1y1x2y2x3y3....xnyn where x1 , x2 are alphabets x1 < x2 <.... < xn and y1y2...yn are integers . y1 < y2 <.... < yn Arrange the output as x1x2...xny1y2...yn

Any suggestions ?

Answer 1

What is n? Assuming that n is the size of the input:

This is called the convolution of a list. In essence, you have to convert a list of pairs (a,1),(b,2),(c,3),(d,4) to a pair of lists (a,b,c,d),(1,2,3,4). It's the same operation as the transpose of a matrix.

Anyway, you have to think of the structure as a k-dimensional array, where k = lg n. The convolution of the array is what you get when you "move" the value at an index i to index i bitwise rotated. In this case, we want to rotate the indices rightward 1 bit. This means that the convolution is a permutation with a maximum cycle length of k. The trick is then selecting one index from each cycle – this will always include 0 and n-1.

EDIT: Actually, what you probably want is to decompose the permutation into a product of transpositions. Then, all you need to do is swaps.