A reader asked us the following question:
This cannot be solved in O(N) time unless the last element is the greatest.
The next greater element is the first element towards the right, which is greater than the current element. To find the next greater element, we will follow the following steps:
1- Create an empty stack.
2- Traverse the elements of an array from right to left.
3- If the stack is not empty and top of the stack is less than or equal to the current element, we will keep on popping the elements until the top element is greater than the current element.
4- If the stack is not empty at the end, then the next greater element will be the top element of the stack.
5- If the stack is empty at the end, the next greater element will be -1.
In each iteration, we will pop some entries from the stack and push new entries. The for loop will traverse N (N= Number of elements in an array) elements. Whereas, the while loop will not traverse N elements in each iteration. So the complexity of this algorithm cannot be O(N^2). It is O(M*N). Here, M (M = Number of elements in a stack that are smaller than the current element) is varying in each iteration, and it is so small that we ignore it. Therefore, we say that the average complexity of this algorithm is O(N).
Let’s dry run our algorithm.
Input 1 ={9, 12, 20, 4, 5, 1}
Stack 0, 0, 0, 0, 0, -1 <----- Top is -1 (Empty Stack)
First Iteration:
next = 1
Stack is empty
∴ result[5] = -1
Stack 0, 0, 0, 0, 0, 1 <----- Top is 1
Second Iteration:
next = 5
(top < next) -> Pop(1) -> Now stack is empty
∴ result[4] = -1
Stack 0, 0, 0, 0, 0, 5 <----- Top is 5
Third Iteration:
next = 4
(top > next)
∴ result[3] = 5
Stack 0, 0, 0, 0, 5, 4 <----- Top is 4
Fourth Iteration:
next = 20
(top < next) -> Pop(4) -> Pop(5) -> Now stack is empty
∴ result[2] = -1
Stack 0, 0, 0, 0, 0, 20 <----- Top is 20
Fifth Iteration:
next = 12
(top > next)
∴ result[1] = 20
Stack 0, 0, 0, 0, 20, 12 <----- Top is 12
Sixth Iteration:
next = 9
(top > next)
∴ result[0] = 12
Stack 0, 0, 0, 20, 12, 9 <----- Top is 9
At the end:
result array {12, 20, -1, 5, -1, -1}
2 Likes