Next greater number

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

Code Samples

• C++