@Pralaybi: While this is a nice solution to the Dutch National Flag problem, the problem the original poster presented, and called the Dutch National Flag problem, is different. What the given problem really amounts to is transposing a 3-by-(n/3) array stored in a linear array into an (n/3)-by-3 array, in-place. For algorithms, google "in situ matrix transposition" and "in place matrix transposition". I'm not sure that an O(n)-time algorithm exists. Dave
On Tuesday, January 15, 2013 2:08:15 PM UTC-6, pralaybi...@gmail.com wrote: > Hi, > > You could try something like this. > > [image: Inline image 1] > > One pass thru the array (jack here, sorry for the bad naming) and you are > done! > > Cheers :) > > > > On Mon, Jan 14, 2013 at 1:37 AM, Ankit Tripathi > <ankittri...@gmail.com<javascript:> > > wrote: > >> Hello everyone, >> Recently I encountered following program : >> Given an integer array of n elements ( where n is a multiple of 3 ), >> example : *a1, a2, a3, a4, b1, b2, b3, b4, c1, c2, c3, c4*. >> You have to rearrange the array in such a manner that the elements of >> array becomes : >> *a1, b1, c1, a2, b2, c2, a3, b3, c3, a4, b4, c4*. >> >> Time complexity = O(n) >> Space complexity = O(1). >> >> I was able to write a code where it took *O(n) time, but in O(n) space*. >> Can anybody suggest me a way to do the code in *O(1) space and O(n) time? >> * >> >> -- >> >> >> > > --
