You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}. Now we create a signature of this array by comparing every consecutive pair of elements. If they increase, write I else write D.?

Rough Algorithm : Take the permutation 1 2 3 .... n. For example if n=5 take permutation 1 2 3 4 5. Call It original sequence. Mark all the continuous occurrences of D in the given signature. Then for each continuous sequence of D, going from left to right reverse the strip corresponding to that in original sequence.Every time make the new sequence as original sequence. Example : Take the above case. Signature = DDIIDI. Take original permutation as 1 2 3 4 5 6 7. Then for first continuous sequence DD reverse the strip 1 2 3 to 3 2 1 hence sequence becomes 3 2 1 4 5 6 7. Then for second sequence D reverse strip 5 6 to 6 5 hence sequence becomes 3 2 1 4 6 5 7. There is no continuous D left we are done and reached the answer. Source : http://learn.hackerearth.com/forum/182/lexicographically-smallest-permutation-given-a-signature/

as the signature is given of length N-1, i can do this in complexity well proportional to N. My algorithm: 1. Read from left to right the array given and write down another array with the value expressed as count of continous Ds and Is , for example if your array is DDIIDI you start traversing and increase the counter and write down as (+2)(-2)(+1)(-1).....+2 for 2 continous Ds, -2 for 2 continous Is and so on. This will have an complexity of N 2. Now you sum this second array....i.e (+2) + (-2)+(+1)+(-1). You get 0 in this case , meaning you need not worry , you can start from any number considering the 1st +2, had it been -2 at start you could have started from 3 and beyond as ecah member should lie in 1 to n. If the sum is negative say -6,means min you need to start from a gap of 7, then you look at 1st item count if it is in negative say -3 , start from min 10 (7+3) else you can start from 7 if the 1st item is +ve. Time complexity N (worst case). So overall time complexity is N.