Next Greater Element in an array

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.

Example

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
the key to this problem is to reduce the number of comparisons.

Solutions

Method 1 : Simple O (n^2)  method
Use two loops. The outer loop runs from 0 to size – 1 and one by one picks all elements from left to right. The inner loop compares the picked element to all the elements to its right side. If the picked element is greater than all the elements to its right side, then the picked element is the leader.

/*Function to print leaders in an array */
void printLeaders(int arr[], int size)
{
  int i, j;
 
  for (i = 0; i < size; i++)
  {
    for (j = i+1; j < size; j++)
    {
        if(arr[i] < arr[j])
          continue;
        else print a[i] "–>" a[j];
         
    }    
  }
}

Method 2 :  Using a stack

1. Take stack A.
2. Initially the stack is empty. Traverse the array from left to right. Do for every element.
   1. if the stack is empty push the element in the stack
   2. if the stack is non empty keep on popping elements from the stack till 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. The next greater element for every popped element would be the current element. If element popped >

Example
for array [2, 25, 20, 11, 21, 3]
stack A -> empty

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.