Given an array ` arr `

of ` n `

integers, print the next greater number for every element. The next greater element of a number ` k `

is the first number to the right of ` k `

which is also larger than ` k `

. If there is no next greater element print ` -1 `

The expected time complexity of the solution is ` O(n) `

#### Example Test Cases

##### Sample Test Case 1

Input Array: ` [1, 5, 3, 4] `

Expected Output: ` [ 5, -1, 4, -1 ] `

Explanation: The next greater number for element ` 1 `

at position ` 0 `

is 5, for element ` 5 `

which is at position ` 1 `

, there is no next greater number, for next element ` 3 `

, the next greater number is ` 4 `

, for element ` 4 `

located at position ` 3 `

, there is no next greater number.

#### Solution

##### Brute Force

The naive way to solve this problem would be to iterate over each index ` i `

of the array and then compute the next greater number by iterating over the array from position ` i + 1 `

onwards. This would involve writing two for loops, with the 2^{nd} for loop nested inside the first loop and the time complexity would be ` O(n^2) `

.

##### Optimized solution

We can optimize the solution of the problem by using a stack.

** At any point of time, an element will be in stack iff we have iterated over that element and we haven’t found the answer for that element yet. As soon as find the next greater number for any element from the stack, we will pop it from the stack**.

Let us call the top element of stack as ` top `

Initially we will push element ` arr[0] `

onto the stack.
When we iterate over the remaining elements ` arr[i] `

for (i >= 1), we know either of the two cases will occur:

`arr[i] > top`

: In this case , the answer for`top`

will be`arr[i]`

. Therefore, we will keep on popping out the`top`

elements from stack until`top`

becomes than`arr[i]`

and mark the answer for all the popped elements as`arr[i]`

and then insert`arr[i]`

onto the top of the stack.-
`top >= arr[i]`

: In this case, we will just push the`arr[i]`

onto the top of the stack