Given an array
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
The expected time complexity of the solution is
Example Test Cases
Sample Test Case 1
[1, 5, 3, 4]
[ 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.
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 2nd for loop nested inside the first loop and the time complexity would be
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
Initially we will push element
arr 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
arr[i]. Therefore, we will keep on popping out the
topelements from stack until
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