1 Test case failing
@anubhavb11
your code is wrong, check this for eg:- arr[] = 10 20 3 30 40 50
answer should be 1 2 1 4 5 6.
Here maintain the stack to store the index of just previous element index for current index element, where the previous index tells us about the element before this current index but greater than that so then the difference between their index will tell you the answer.
So just maintain the index of previous element at the top of the stack which is larger than the current index element.
You can have a look at my code if you want https://ide.codingblocks.com/s/247586
@anubhavb11
please let me know if you have some query. Otherwise please mark this doubt as resolved.
i did not get the code nor thee logic i am so confused how difference will give me the ans
@anubhavb11
okay let take an example:
In above image you can see that for eg i=5, so for i=5 we have a span of 4 (start from 2 till 5). So we just need to know the index of previous stock price(there should not be any another between them which is greater than the price at i) which is greater than current 'i’th price.
We see that S[i] on day i can be easily computed if we know the closest day preceding i, such that the price is greater than on that day than the price on day i. If such a day exists, let’s call it h(i), otherwise, we define h(i) = -1.
The span is now computed as S[i] = i – h(i). See the above diagram.
Our Algo will be like:- When we go from day i-1 to i, we pop the days when the price of the stock was less than or equal to price[i] and then push the value of day i back into the stack.
I hope you have got some idea from this.