Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### Darth's blog

By Darth, history, 11 months ago, ,

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 105.

My solution:

Solution

My implementation:

Implementation

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

Thaks!

•
• +3
•

 » 11 months ago, # |   +8 Your solution fails on a case like this:44 1 2 5Since 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.
•  » » 11 months ago, # ^ |   +3 Ahmad thanks. :D
 » 11 months ago, # |   +5 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
•  » » 11 months ago, # ^ |   0 p00r thanks.