[Arrays] [InterviewBit] Increasing decreasing arrays

Given relationship between consecutive elements of an array, generate the array

Problem statement:

Given a positive integer $n$ and a string $s$ consisting only of letters $D$ or $I$, you have to find any permutation of first $n$ positive integer that satisfy the given input string.
$D$ means the next number is smaller, while $I$ means the next number is greater.
Notes

• Length of given string $s$ will always equal to $n - 1$
• Your solution should run in linear time and space.

Initial Thoughts:

What? How will I generate an array given only the relationship between consecutive elements? Plus they're also dependent upon the elements far after and before the elements. How?

Actual Solution:

Meh. Well after I thought a lot about it, generation can be a greedy procedure. You know how much in total increase is to be done. You also know how much decrease is to be done. The main problem is that once an increase is required, an increase must be done. So, basically you can't increase after the maximum element et cetera.

So I know that $i$ increases must be done after an element and $d$ decreases must be done after an element. So I must leave a gap of $i$ above the element $e$ I will select for the current position, and a gap of $d$ below $e$. That means, I've to select $d+1$th element. 

Meh.

So, the first element will be the $d+1$th element. All increases will go up, and all decreases will go down. So, I can create two pointers $uptr$ that goes up and $dptr$ that goes down. $uptr = d+2$ and $dptr = d$ initially. Everytime, an $I$ comes in the string, I put $uptr$ value in the current position and increase $uptr$ by $1$. 

Similarly, everytime I see a $D$ in the string, I put $dptr$ in the current position and decrease $dptr$ by $1$.

Done. EOD. Hence proved. Fuck off.

Code: