Hello guys.

I was trying to solve this problem by Just Contest 2.0, about to find the next greater element. For exemple:

Array = [1, 5, 4, 7, 9]

Ans = [5, 7, 7, 9, -1]

-The input is 10^{5}.

My solution:

**Solution**

My implementation:

**Implementation**

Someone can explain-me where I did wrong? Or my idea is not correct?

Thaks!

Your solution fails on a case like this:

4

4 1 2 5

Since the answer for 1 is 2 and 1 is not greater than 4 and 2 is also not greater than 4, it'll say that the answer for 4 is -1 when it is actually 5. Here's a (probably correct) solution for how you could solve this problem:

SpoilerNotice that a[i] is bounded by at most 50. So for each distinct numerical value, you can iterate backwards in your array and update your answer for a number every time you hit a number greater than the one you're testing. So for the break case let's say we're processing 1:

We see 5 and note that it's greater than 1 so we store it as our answer. Then we see 2 and note that it's also greater than 1 so we store that as our answer. Then we get to a position that actually has a 1 so we set the answer for that index to be 2.

And since there are at most 50 distinct numbers, you're only doing 50 * 10^5 iterations which is definitely doable in a second.

Ahmad thanks. :D

O(n) solutionYou can use a stack. Push the indices into the stack from left to right until its corresponding values are non-increasing. If you find an index whose value is higher than the topmost index's value, recursively pop until non-increasing condition is maintained in the stack and insert the new index. For all the indices popped by an index i, A[i] is the corresponding value in their Ans array. -1 for others

p00r thanks.