Next greater element

Problem:

Given an array, print the next greater element for every element. Elements for which no greater element exist, print next greater element as -1.

For the elements of the array [4, 5, 2, 25, 20, 11, 13, 21, 3] greater elements are as follows.

4 --> 5

5 --> 25

2 --> 25

25 --> -1

20 --> 21

11 --> 13

13 --> 21

21 --> -1

3 --> -1

Solution : O(n)

1. Take stack A.

2. Initially the stack is empty. Traverse the array from left to right. Do for every element

a. if the stack is empty push the element in the stack

b. if the stack is non empty keep on popping elements from the stack till element popped < current element. The next greater element for every popped element would be the current element. If element popped > current element. Push popped element and then current element on the stack.

3. When the traversal is complete, if the stack is nonempty pop elements from the stack and set the values of next greater element for these popped element as -1.

eg. for array [2, 25, 20, 11, 21, 3]

stack A -> emtpy

1. push element 2 on stack A->2

2. pop 2 from the stack. Compare it with 25 since 2 < 25 set next greater element of 2 as 25.

A->25

3. pop 25 from the stack. 25 > 20 . Push 25 on the stack. Push 20 on the stack.

A->25->20

4. pop 20 from the stack. 20>11. Push 20 on the stack. Push 11 on the stack.

A->25->20->11

5. pop 11 from the stack. 11 < 21. Set next greater element of 11 as 21. Pop 20 from the stack. 20 < 21. Set next greater element of 20 as 21. Pop 25 from the stack. 25 > 21. Push 25 on stack. Push 21 on stack.

A->25->21

6. pop 21 from the stack. 21 > 3. Push 21 on stack. Push 3 on stack.

A->25->21->3

Set the value of next greater elements for all the elements present in the stack as -1.