This is a special case of shuffling problem. In shuffling problem we have to merge k (here k = 3) parts of array such that each kth element is from the same sub-array and in same order. For eg - a1 a2 a3 a4 b1 b2 b3 b4 c1 c2 c3 c4 should become => a1 b1 c1 a2 b2 c2 a3 b3 c3 a4 b4 c4.
Usually shuffling problem can be solved only in O(n*logn) time without additional space, but here you have an added advantage. You know what the sequence should look like exactly. So here goes the O(n) solution with constant space. 1- Take 2 pointers p1 and p2 initialize both of them to index 1 (second element) 2- now for each element at p2 find the right index where it should go and put it thr. The right index is - (k*p2 -1) % (n-1); // k=3 here 3- Keep doing it until p2 becomes same as p1 again. 4- Now advance p1 till the elements are in order 0 1 2 0 .... 5- if p1 is less than n-1 than set p2 = p1. Repeat thru step 2-5 again. Here is a primitive C code to do the same. int p1 = p2 = 1; int preVal, next, temp; while (p1 < n) { preVal = a[p1]; p2 = p1; do{ next = (k*p2 -1) % (n-1); // k=3 here temp = a[next]; a[next] = preVal; preVal = temp; p2 = next; } while (p2 != p1) while(p1 < n) { if( ((a[p1] - a[p1-1]) == 1) || (a[p1] - a[p1-1]) == -2)) // elements are in sequence 0 1 2 0 p1++; else break; } } Feedback welcome :-). - Ravindra On Wed, Nov 2, 2011 at 6:43 PM, shady <sinv...@gmail.com> wrote: > any solutions for this ? > dutch national flag problem could be done in O(n) time and O(1) space by > considering two pointers, but how to do this (reverse dutch national flag > problem) ? > > > On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal <srn...@gmail.com> wrote: > >> Suppose we are given a string 000011112222. >> >> Make it 012012012012 in O(n) time and O(1) space. >> Sanju >> :) >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algogeeks@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.