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!
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:
Notice 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
You 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